4
$\begingroup$

I would like to list all ways of writing $n$ as the sum of 3 squares. This is slightly different from finding just one:

My current implementation is the naive one which runs in $O(n^{3/2})$ time: Write all numbers $n = x^2 + y^2 + z^2$ with

  • $x < \sqrt{n}$
  • $y < \sqrt{n - x^2}$
  • $z < \sqrt{n - x^2 - y^2}$

Perhaps there is a more efficient way using Quaternions or matrices or something?

Finding All Representations

The linked questions efficiently compute one representation $n = x^2 + y^2 + z^2$. However, I am hoping to find a complete list of all representations and I would like to know if we can do any better than the naïve algorithm.

$\endgroup$
  • 1
    $\begingroup$ Possible duplicate of Is there an algorithm for writing a number as a sum of three squares? $\endgroup$ – Igor Rivin Oct 2 '15 at 19:52
  • $\begingroup$ Duplicate of mathoverflow.net/questions/110239/… $\endgroup$ – Igor Rivin Oct 2 '15 at 19:52
  • 2
    $\begingroup$ @IgorRivin Can the algorithm for finding one representation be turned into an algorithm for finding all representations? $\endgroup$ – john mangual Oct 2 '15 at 19:54
  • $\begingroup$ A fair point, so the question is not quite a duplicate. $\endgroup$ – Igor Rivin Oct 2 '15 at 20:08
  • $\begingroup$ Somewhat less naive is to loop over $x < \sqrt{n}$. For each $m = n - x^2$ you then want to find all representations $m = y^2 + z^2$, which can be obtained by factoring $m$ over the Gaussian integers. I'm pretty sure we don't know the true complexity of that (not even of factoring over the integers), but it's certainly $o(m)$. $\endgroup$ – Robert Israel Oct 2 '15 at 20:12
7
$\begingroup$

The number of representation can be as big as $\sqrt{n},$ so this is a lower bound on the complexity of any algorithm. Now, the algorithm is to iterate through all $k\leq \sqrt{n},$ and try to represent $n-k^2$ as a sum of squares (in all possible ways). This is equivalent to factoring, so the complexity will be not that bad above optimal (factoring is "hard", but not so hard compared to $\sqrt{n},$ indeed, this algorithm runs in time $O(n^{1/2 + \epsilon})$ for any $\epsilon > 0.$)

$\endgroup$
  • $\begingroup$ For each of the numbers $k < \sqrt{n}$ I can factor $n - k^2$ which I can do in $\sqrt{n}$ time, so the total run time is $\sqrt{n} \times \sqrt{n} = n$. $\endgroup$ – john mangual Oct 2 '15 at 20:35
  • $\begingroup$ @johnmangual it's a lot better than that, see the edited version. $\endgroup$ – Igor Rivin Oct 2 '15 at 21:01
  • $\begingroup$ The factorization step takes $log(n)$ time or something ? $\endgroup$ – john mangual Oct 2 '15 at 21:20
  • $\begingroup$ @johnmangual wikiwand.com/en/Integer_factorization#/… $\endgroup$ – Igor Rivin Oct 2 '15 at 21:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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