Need help understanding Sum of Squares function r_2(n) - MathOverflow [closed] most recent 30 from http://mathoverflow.net 2013-05-25T13:39:08Z http://mathoverflow.net/feeds/question/88164 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/88164/need-help-understanding-sum-of-squares-function-r-2n Need help understanding Sum of Squares function r_2(n) Awk34 2012-02-10T23:46:45Z 2012-02-10T23:46:45Z <p>I am trying to understand how to quickly find the number of two squares that can be added to form a number 'n'. This is my reference: <a href="http://mathworld.wolfram.com/SumofSquaresFunction.html" rel="nofollow">http://mathworld.wolfram.com/SumofSquaresFunction.html</a></p> <p>I have written a function that I believe gives me my proper answers, but I need it to run faster. Pretty much what it does is it goes through possible numbers below Square Root of n, and sees if those to numbers squared equals n. I then add 4 to the sum, since it includes when any number is negative (positive when squared). If you understand Java, here is my code:</p> <pre><code>static int SquaresR2(int n) { int sum = 0; outer: for(int a=0; a&lt;Math.sqrt(n)-1; a++) { for(int b=0; b&lt;Math.sqrt(n)-1; b++) { if( a*a + b*b == n ) { if(a&gt;b) break outer; sum+=4; System.out.println(n+" = "+a+"^2 + "+b+"^2"); } } } sum*=2; if(Math.sqrt(n)==(int)Math.sqrt(n)) sum+=4; return sum; } </code></pre> <p>On Wolfram MathWorld it says that finding the Sum of Squares k=2 relates to factoring n to \$n=2^{a_{0}} p_{1}^{2_{a_{1}}} ... p_{r}^{2_{a_{r}}} q_{1}^{b_{1}} ... q_{s}^{b_{s}}\$ where the \$p_{i}\$s are primes of the form 4k+3 and the \$q_{i}\$s are primes of the form 4k+1. I have (almost) no idea what this means.</p> <p>It also talks about \$B=(b_{1}+1)(b_{2}+1)...(b_{r}+1)\$, which I also have no understanding of.</p> <p>I am thinking it has something to do with factoring n using primes. I am a high school senior taking Calculus 1.</p> <p>Please help me! Thank you in advance.</p>