Need help understanding Sum of Squares function r_2(n)

2012-02-10T23:46:45Z

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.

Please help me! Thank you in advance.

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

Need help understanding Sum of Squares function r_2(n)