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

- Is there an algorithm for writing a number as a sum of three squares?
- Efficient computation of integer representation as a sum of three squares
- Rabin and Shallit Algorithm

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.

onerepresentation be turned into an algorithm for findingallrepresentations? $\endgroup$ – john mangual Oct 2 '15 at 19:54