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 code-golf, so shortest answer as measured in bytes wins.
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.
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]]
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.
JqS[GZ2CB)++j~[
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
f=n=>(m=n)?[...Array(++m*m).keys()].some(i=>(i%n)**2+(~~(i/n))**2==n):0
Not great but might as well post it since I spent an hour trying.
let a t=Seq.allPairs[0..t][0..t]|>Seq.tryFind(fun(f,s)->f*f+s*s=t)
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.
Ė2Ṛ²ʂƇ
Very slow for large inputs.
Ė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
