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.

First Wave:

For k=169, we have the sum of 169 1's. We need to trade 4 of the 1's to get the next square sum, 165*1+4, so there are square sums with 168 and 167 terms. By the same argument, 161*1+2*4 skips over square sums with 165 and 164 terms. With this technique of substituting 4 for 4 ones covers the k's:

k=169, 166, 163, 160, ..., 43->1+42*4

Once down to k=163 where we have at least two 4's, Substituting 9 for 1+2*4 on each of these give a net loss of two on k:

k=161, 158, 155, 152, ..., 41->40*4+9

Starting with k=155, we can do another substitution on 9 for 1+2*4 on the last set to cover:

k=153, 150, 147, 144, ..., 42->3*1+37*4+2*9

This spread does devastating damge once we get started. 168, 167, 165, 164, 162, 159, 152 are the only k>40 where 169 can not be written k terms of squares.

Second Wave:

Now start with the sum 69*1+100 and begin the above game again. By doing just the 4's, we cover:

k=70, 67, 64, 61, ..., 19->1+17*4+100

Starting with k=64, we do the 9 game:

k=62, 59, 56, 53, ..., 17->15*4+9+100

Starting with k=56, we do the second 9:

k=54, 51, 48, 45, ..., 18->3*1+12*4+2*9+100

Notice that our last gap in this wave is at 52, well within the coverage of the first wave. So, except for the k mentioned in the first wave, we have all k covered for k>16.

Third Wave:

Starting with the sum 48*1+121, we can use the same constructions in the first two waves. The last gap is at k=31, and covered by the second wave. The last k covered in this wave is k=12 given by the sum 2*1+7*4+2*19+121.

Last Wave:

k=1->169
k=2->25+144
k=3->9+16+144
k=4->3*16+121
k=5->1+2*16+36+100
k=6->4*4+9+144
k=7->3*1+4+2*9+144
k=8->3*1+6*4+121
k=9->4*1+3*4+9+144
k=10->4*1+3*4+2*16+121
k=11->3*1+4*4+9+16+25+100

Conclusion: We can write 169 as the sum of k square terms, for k<170, k not equal to 168, 167, 165, 164, 162, 159, 152. Whew ... that took way too much time :-)

Posted by owl on 2004-11-05 08:12:46