## Need help understanding Sum of Squares function r_2(n) [closed]

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: http://mathworld.wolfram.com/SumofSquaresFunction.html

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:

static int SquaresR2(int n) {
int sum = 0;
outer:
for(int a=0; a<Math.sqrt(n)-1; a++) {
for(int b=0; b<Math.sqrt(n)-1; b++) {
if( a*a + b*b == n ) {
if(a>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;
}


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.

It also talks about $B=(b_{1}+1)(b_{2}+1)...(b_{r}+1)$, which I also have no understanding of.

I am thinking it has something to do with factoring n using primes. I am a high school senior taking Calculus 1.

-
 try math.stackexchange.com/questions?sort=active – Will Jagy Feb 10 2012 at 23:49 @WillJagy Why there instead of here? – Awk34 Feb 11 2012 at 0:27 This site is for research questions by and for professional mathematicians. MSE has a wide range, sometimes they are willing to throw in substantial tutoring. If you doubt my description, take a look at a dozen questions that have not been closed, see in how many you understand the words. Also the FAQ. – Will Jagy Feb 11 2012 at 0:34 As requested, math.stackexchange.com/questions/107982/… – Will Jagy Feb 11 2012 at 0:44 As general hints in writing fast algorithms: 1) If you are computing successive squares use the formula $(a+1)^2=a^2 + 2a + 1$ and the fact that $a^2$ is already computed. 2) Multiplication by powers of 2 can be done by right shifts. – Ralph Feb 11 2012 at 1:47
show 1 more comment