Problem of the Week 841

How many squares?

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:

169 = 13² = 5²+12² = 3²+4²+12² = 1²+2²+8²+10² = 1²+2²+2²+4²+12²

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.

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.