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.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Possible duplicate of Is there an algorithm for writing a number as a sum of three squares? $\endgroup$
    – Igor Rivin
    Commented Oct 2, 2015 at 19:52
  • $\begingroup$ Duplicate of mathoverflow.net/questions/110239/… $\endgroup$
    – Igor Rivin
    Commented Oct 2, 2015 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
    Commented Oct 2, 2015 at 19:54
  • $\begingroup$ A fair point, so the question is not quite a duplicate. $\endgroup$
    – Igor Rivin
    Commented Oct 2, 2015 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
    Commented Oct 2, 2015 at 20:12

1 Answer 1

Reset to default
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.$)

Improve this answer
$\endgroup$
4
  • $\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
    Commented Oct 2, 2015 at 20:35
  • $\begingroup$ @johnmangual it's a lot better than that, see the edited version. $\endgroup$
    – Igor Rivin
    Commented Oct 2, 2015 at 21:01
  • $\begingroup$ The factorization step takes $log(n)$ time or something ? $\endgroup$
    – john mangual
    Commented Oct 2, 2015 at 21:20
  • $\begingroup$ @johnmangual wikiwand.com/en/Integer_factorization#/… $\endgroup$
    – Igor Rivin
    Commented Oct 2, 2015 at 21:29

You must log in to answer this question.

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