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 = 132 = 52+122 = 32+42+122 = 12+22+82+102 = 12+22+22+42+122

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.

The Math Forum

2 October 1998