3
$\begingroup$

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.

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

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank, but for $N = 10^9$ O(N) is very slow. $\endgroup$
    – Dmitry
    Jun 5, 2012 at 15:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .