Sum of squares

Goal: Write a given natural number as sum of squares. Thanks to Lagrange, Fermat and Legendre we know that you can write any positive integer as sum of (one), two, three, or maximal four squares of integers.

Your task is to write a program/function which takes a natural number via stdin/argument and outputs/returns a list of one to four numbers, where the sum of the squares of those numbers equals the input number. But you have to find the shortest possible example, that means if you can write a number as three squares, you may not output the four squares version.


1 : 1
2 : 1,1
3 : 1,1,1
4 : 2
5 : 1,2
6 : 1,1,2
127 : 1,3,6,9
163 : 1,9,9
1234 : 3,35
1248 : 8,20,28
  • 1
    \$\begingroup\$ I think this will have different answers from the other question because there's no time limit so brute force is possible. \$\endgroup\$ – xnor Mar 31 '15 at 19:26
  • 1
    \$\begingroup\$ Between the lack of a time constraint and the minimality of the number of squares I think it's borderline okay to keep, but I'm not sure what others think. \$\endgroup\$ – Sp3000 Mar 31 '15 at 19:27
  • \$\begingroup\$ I just read the linked question in detail, (I did not find it before, because I was looking for 'sum of squares' and similar keywords), I'm gonna close this question if nobody opposes. \$\endgroup\$ – flawr Mar 31 '15 at 19:32

JavaScript: 141

function x(i){var a=0,b,c,d;for(;a<i;a++)for(b=0;b<i;b++)for(c=0;c<i;c++)for(d=0;d<i;d++)if(a*a+b*b+c*c+d*d==i){console.log(a,b,c,d);return}}
  • \$\begingroup\$ Your function does not return the 'shortest' example. E.g. for the input 11 your function returns [0,1,1,3] where the shortest answer would be [1,1,3]. \$\endgroup\$ – flawr Mar 31 '15 at 19:26
  • \$\begingroup\$ I assume the zeros returned don't count, as they don't contribute to the sum. \$\endgroup\$ – captncraig Mar 31 '15 at 19:27
  • \$\begingroup\$ Does it always produce the shortest, ignoring 0s? \$\endgroup\$ – Sparr Mar 31 '15 at 19:29
  • \$\begingroup\$ yes, by brute force. \$\endgroup\$ – captncraig Mar 31 '15 at 19:30

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