Take the 2-minute tour ×

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.

share|improve this question
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
add comment

2 Answers

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.

share|improve this answer
Thank, but for $N = 10^9$ O(N) is very slow. –  Dmitry Jun 5 '12 at 15:22
add comment

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.

share|improve this answer
add comment

Your Answer


