# Sum of two squares

Given a nonnegative integer $$\n\$$, determine whether $$\n\$$ can be expressed as the sum of two square numbers, that is $$\\exists a,b\in\mathbb Z\$$ such that $$\n=a^2+b^2\$$.

   0 -> truthy
1 -> truthy
2 -> truthy
3 -> falsy
4 -> truthy
5 -> truthy
6 -> falsy
7 -> falsy
11 -> falsy
9997 -> truthy
9999 -> falsy


Relevant OEIS sequences:

This is , so shortest answer as measured in bytes wins.

• Commented Feb 7, 2022 at 8:28
• Do we have to handle negative inputs? Commented Feb 7, 2022 at 8:40
• Can we output 2 consistent values instead of 'truthy' and 'falsy'? Commented Feb 7, 2022 at 10:10
• @DominicvanEssen, I think it's default for decision-problem (see tag info). Commented Feb 7, 2022 at 10:45
• @hyper-neutrino No, nonnegative integers only. Updated the question to specify this. Commented Feb 7, 2022 at 19:16

# Desmos, 47 bytes


f(n)=\prod_{a=0}^n\prod_{b=0}^n\{aa+bb=n:0,1\}


The leading newline is necessary for the piecewise to paste properly.

Outputs 0 for truthy and 1 for falsey.

Try it on Desmos!

The ∏ trick didn't work, maybe due to the \{aa+bb=n:0,1\} piecewise. Avoiding it with sign(aa+bb-n)^2 or 0^{(aa+bb-n)^2} ended up longer.

f n=and[gcd(k^2)n/=k|k<-[3,7..n]]


Try it online!

Checks that all $$\k\$$ that are $$\3 \bmod 4\$$ have $$\\gcd(k^2,n)\neq k\$$. This comes from the characterization of sums of two squares as numbers whose prime factorization doesn't have any $$\3 \bmod 4\$$ prime raised to an odd power. If such a $$\p^a\$$ appears in the factorization, then $$\p^a \ \equiv 3 \bmod 4\$$, and $$\k=p^a\$$ will fail the condition.

Outputting True/False reversed could save a byte by using or rather than and.

# Burlesque, 15 bytes

JqS[GZ2CB)++j~[


Try it online!

Horribly inefficient for falsy, but works

J   # Duplicate input (n)
qS[ # Quoted square
GZ  # Generate squares [0..n)
2CB # All combinations of pairs
)++ # Sum each pair
j   # Swap stack
~[  # n in list


# JavaScript (V8), 71 bytes

f=n=>(m=n)?[...Array(++m*m).keys()].some(i=>(i%n)**2+(~~(i/n))**2==n):0


Try it online!

Not great but might as well post it since I spent an hour trying.

# F#, 66 bytes

let a t=Seq.allPairs[0..t][0..t]|>Seq.tryFind(fun(f,s)->f*f+s*s=t)


Try it online!

Straight-forward: create two lists from 0 to total, Seq.allPairs gets the Cartesian product between the two, and Seq.tryFind tries to find the pair that, when squared and added together, equals the total t.

# Thunno 2, 6 bytes

Ė2Ṛ²ʂƇ


Try it online!

Very slow for large inputs.

#### Explanation

Ė2Ṛ²ʂƇ  # Implicit input
Ė       # Push [0..input]
2Ṛ     # Combinations with
# replacement with
# a length of two
²    # Square (vectorised)
ʂ   # Sum each inner list
Ƈ  # Contains the input?
# Implicit output