20091105, 07:01  #1 
Aug 2006
1761_{16} Posts 
Sums of three squares
There's a wellknown formula for the number of ways that a number can be expressed as the sum of two squares: the product of one more than the exponents of the primes = 1 mod 4, assuming that all primes = 3 mod 4 appear to an even power (and 0 if any appear to an odd power).
Is there a similarly nice formula for sums of three squares? I was trying to do some calculations with them but the inefficiency of my current program makes that difficult. I'm able to use some properties of such numbers (removing factors of 4, checking mod 8, using an efficient sum of two primes subroutine to remove some cases) but it's still slow  getting to ten million will take all night, where with sums of two primes that would take 25 seconds. 
20091105, 12:47  #2  
Nov 2003
2^{2}×5×373 Posts 
Quote:
Last fiddled with by R.D. Silverman on 20091105 at 12:52 Reason: typo 

20091106, 13:46  #3 
Feb 2005
2^{2}×3^{2}×7 Posts 
See formula (35) at http://mathworld.wolfram.com/SumofSquaresFunction.html

20091106, 14:39  #4 
Aug 2006
3^{2}·5·7·19 Posts 
Let me look at that formula and see if there is a good way to translate between it and my problem (essential solutions, not including sign and ordering).
Since this formula applies only for squarefrees, how do I solve r_3(n * s^2)? Is there a good upper bound on the number of representations? Even a weak one like r_3(n) < n would be nice. Last fiddled with by CRGreathouse on 20091106 at 14:55 
20091106, 17:48  #5  
Dec 2008
1101000001_{2} Posts 
Quote:
I should note that the methods used to achieve an upper bound on the number of representations as the sum of three squares of primes can be modified without much difficulty to provide a corresponding estimate (of the same quality, at worst) for the sum of three squares. The reason for this is that the situation becomes harder if we restrict some variables to primes. Thus, I am sure that the problem of the sum of three squares of primes (or a variant of this problem, at best) is treated in the HR text. Last fiddled with by flouran on 20091106 at 17:49 

20091106, 17:53  #6  
Feb 2005
374_{8} Posts 
Quote:
Ordering is also possible to take into account by considering cases with distinct/equal squares. 

20091106, 19:20  #7  
Aug 2006
3^{2}×5×7×19 Posts 
Quote:
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? 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Sums of all Squares  davar55  Puzzles  183  20191212 22:31 
Regarding Squares  a1call  Miscellaneous Math  42  20170203 01:29 
Basic Number Theory 12: sums of two squares  Nick  Number Theory Discussion Group  0  20161211 11:30 
squares or not squares  m_f_h  Puzzles  45  20070615 17:46 
Fibonacci sums?  TTn  Math  2  20021025 21:47 