Find all integers 1<=k<=169 for which 169 is not the sum of k nonzero squares.

The squares are not necessarily unique. For example k=5: 169=1+4+4+16+144.

This should be done without a brute force program.

Nobody was posting any comments on here, so I thought I would start, even if I had little idea what I was doing.  So here goes:

The square numbers (that pertain to this problem) are: 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169.

25 can be written as 9 + 16 because 3^2 + 4^2 = 5^2.  It is a pythagorean triple.  100 = 64 + 36.  169 = 144 + 25.

Perhaps this problem has something to do with pythagorean triples.  There are even other sums besides those.  9 = 4 + 4 + 1.  I don't know.

I hope this helps someone else get an idea and run with it.

Posted by Dustin on 2004-11-04 21:20:34