Timeline for Listing all solutions to $n = x^2 + y^2 + z^2 $ with integers
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:58 | history | edited | CommunityBot |
replaced http://mathoverflow.net/ with https://mathoverflow.net/
|
|
| Apr 13, 2017 at 12:19 | history | edited | CommunityBot |
replaced http://math.stackexchange.com/ with https://math.stackexchange.com/
|
|
| Oct 2, 2015 at 20:21 | comment | added | john mangual | @RobertIsrael It sounds like an improvement but I compute $ \sum \sqrt{n - x^2} \approx \mathrm{Area}(\circ) = O( n) $ as an estimate of the runtime. Not that I am any kind of expert. | |
| Oct 2, 2015 at 20:15 | answer | added | Igor Rivin | timeline score: 7 | |
| Oct 2, 2015 at 20:12 | comment | added | Robert Israel | 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)$. | |
| Oct 2, 2015 at 20:08 | comment | added | Igor Rivin | A fair point, so the question is not quite a duplicate. | |
| Oct 2, 2015 at 20:07 | review | Close votes | |||
| Oct 2, 2015 at 20:12 | |||||
| Oct 2, 2015 at 19:59 | history | edited | john mangual | CC BY-SA 3.0 |
explaining why this is not duplicate
|
| Oct 2, 2015 at 19:54 | comment | added | john mangual | @IgorRivin Can the algorithm for finding one representation be turned into an algorithm for finding all representations? | |
| Oct 2, 2015 at 19:52 | comment | added | Igor Rivin | Duplicate of mathoverflow.net/questions/110239/… | |
| Oct 2, 2015 at 19:52 | comment | added | Igor Rivin | Possible duplicate of Is there an algorithm for writing a number as a sum of three squares? | |
| Oct 2, 2015 at 19:44 | history | asked | john mangual | CC BY-SA 3.0 |