Thread: Sums of three squares View Single Post
2009-11-06, 19:20   #7
CRGreathouse

Aug 2006

32·5·7·19 Posts

Quote:
 Originally Posted by maxal Consider different cases depending on the number of nonzero squares in the expansion. If the number of nonzero squares is k, then this expansion is counted 2^k times if signs are taken into account. Ordering is also possible to take into account by considering cases with distinct/equal squares.
Of course I'm not enumerating the cases, so telling properties of each isn't obvious. I'll assume n is a positive integer.

If n is a square, there are 6 representations (1 unique) of the number as 0^2 + 0^2 + a^2. If n is twice a square, there are 12 representations (1 unique) of the number as 0^2 + a^2 + b^2, |a| = |b|.

So I guess I can use these and the algorithm for unique representations as two squares to determine the number of unique and nonunique representations as the sum of three squares, the least of which must be 0. So using the formula for r_3 I can determine the number of nonunique representations of n as the sum of three nonzero squares (and the corresponding number of unique representations skipped).

The number of representations as a^2 + b^2 + c^2 with |a| = |b| but |c| distinct from |a| and |b| can be counted directly. The number of representations as a^2 + b^2 + c^2 with |a| = |b| = |c| is 8 if n is thrice a square and 0 otherwise. The total can be subtracted from the above and divided by 48 to get the number of unique representations of the form a^2 + b^2 + c^2 with 0 < a < b < c; the skipped totals can be added on and I'm done.

Computational analysis:
r_3(n) can be computed in time O(n^.25) with Shanks' method. r_2(n) can be computed in time O(n^o(1)). The case with two equal squares can be computed in time O(sqrt(n) log(n)^2) -- the log term is improvable but realistically at the small sizes this is practical at the square root is likely to be quadratic rather than Karatsuba or Toom. So this case dominates the analysis. Is there a better way to count this case?