# Number of integer solutions: $x^2 + y^2 + z^2 = N$

Help me please with some ideas to find number of integer solutions.

$x^2 + y^2 + z^2 = N$

Time limit - $1$ second, $N \leq 10^9$.

My wrong algorithm:

1) Calculate prime numbers on $(0,\sqrt{N})$

2) Compute $\sqrt{N}$ numbers $A_i = N-z^2, z = \sqrt{N}$.

3) For all $A_i$ check that it not include primes $4k+3$ in odd powers.

4)Find answer for each $A_i$ with brute force.

Running time of algorithm $\approx 1.7$ seconds but it is bad.

-
Do you know any character theory? If you do there is a simple method in Ireland and Rosen's excellent book. –  Eugene Jun 5 '12 at 15:02
Thank, but I don't know character theory. Is it really need for solving this problem ? –  Dmitry Jun 5 '12 at 15:08
I'm sure there are probably other methods. This is the one I know though. Sorry. –  Eugene Jun 5 '12 at 15:11
Thank you for your answer, I will to try read this book) –  Dmitry Jun 5 '12 at 15:17

If you don't want too involved math and just look at it as an algorithm question, the way to do this would probably be like this:

int upper_bound = ceil (sqrt(N/3));
int count = 0;

for (int i = 0; i < upper_bound; i++) {
int i2 = i * i;
int j = i;
int k = floor (sqrt(N-i2));

while (j <= k) {
int j2 = j * j;
int k2 = k * k;
int sum = i2 + j2 + k2;

if (sum < N) {
j ++;
} else if (sum > N) {
k --;
} else {
count ++;
j ++;
}
}
}

return count;


Number of loop iterations is roughly upper_bound$^2$/2 which is about N/6. Should do it.

-
Thank, but for $N = 10^9$ O(N) is very slow. –  Dmitry Jun 5 '12 at 15:22

Here's a paper Some Formulae... that gives an explicit formula that may be easier to compute.

It also has one for the number of partitions into 2 squares, which you could use in your step 4) if that's easier.

You can consult A000164 and A000161 at OEIS for more references.

-