Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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
1  
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

2 Answers 2

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

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.