[ynhtgpyy] Sum of four squares, with hints

To express a number as the sum of two squares, prime factorization is very important.  Use the Brahmagupta-Fibonacci identity (Diophantus identity) to combine primes.  I don't know of a way more efficient than brute force for finding how to express primes (of the form 4n+1) as a sum of two squares.  There is also the case (Sum of Two Squares Theorem) of a prime of the form 4n+3 raised to an even power.  But those are easy: (p^(n/2))^2 + 0^2.

To know whether a number can be expressed as the sum of 3 squares (Legendre's Three Squares Theorem), first divide out powers of 4, then examine the reminder mod 8.  7 is the problematic remainder: if and only if the remainder is 7, then the original number cannot be expressed as a sum of 3 squares.  Otherwise it can be.  I don't know of a way more efficient than brute force how one would go about finding the 3 squares if it is possible.

Finally, all numbers can be expressed as a sum of 4 squares (Lagrange Four Squares Theorem), though again, I don't know of efficient way to find one or all the ways a number can be expressed as a sum of 4 squares.  Often, there are many ways to express a number as the sum of 4 squares.

Here are the numbers 0 though 1849, each number's prime factorization, each number expressed in the form (4^a)*(8b+c) that makes it straightforward to apply Legendre's theorem, and each number expressed as a sum of four or fewer squares.

Previously, without factorization, with source code.