Find the first integer k for which 169 is not the sum of k nonzero squares.Background: 169 is the first integer that is a sum of 1, 2, 3, 4, and 5 nonzero squares:

This fact is important, for it can be used to prove that EVERY integer past 169 is a sum of 5 nonzero squares. Of course, a computer can and should be used for #841. The question is really an algorithmic one: design an efficient algorithm for the problem.

169 = 13 ^{2}= 5^{2}+12^{2}= 3^{2}+4^{2}+12^{2}= 1^{2}+2^{2}+8^{2}+10^{2}= 1^{2}+2^{2}+2^{2}+4^{2}+12^{2}My source, Emil Grosswald's book on sums of squares (Springer), says that writing 169 as a sum of 1, 2, 3, 4, 5, 6, 7, ... squares is amusing at first but eventually becomes tedious. But a clever computer program will handle the job in short order (for modest sized integers).

© Copyright 1997 Stan Wagon. Reproduced with permission.

2 October 1998