Ken's POTW


Sums of Squares
The current Macalaster Problem of the Week (#841) reads:

Find the first integer k for which 169 is not the sum of k nonzero squares.

The squares are not necessarily unique. For example 169=1+4+4+16+144. Here are some extensions I think are also worth investigating:

  1. The above problem.
  2. For each k from 1 to 10 (and farther?), find the first integer which is the sum of 1,2,...,k nonzero squares.
  3. Find the integer from 1 to 100 which can be decomposed into sums of 1,2,...,k nonzero squares, where k is a maximum.
  4. Find the integer from 1 to 100 which can be decomposed into the most different sums of squares (not necessarily 1,2,...,k).
The Macalaster problem suggests that behind the decompositions is the request for an efficient computer algorithm. If you find a good one, please send it along.

Source: Based upon Macalester College Problems of the Week #841.


Solution received from Philippe Fondanaiche, Paris, France:
SUMS OF SQUARES

1) For k=1,2,3 the solution is unique :169 = 144 + 25 = 144 + 16 + 9
    For k>3, the number of solutions is progressively increasing and in the
range of 80 - 100 , there is a kind of plethora.We can easily demonstrate
that we can go from the level k to the level k+3 by transforming the use of
the square 4 in the use of 4 squares 1,from the level k to the level k+2 by
transforming 9 in 2x4 + 1 and from the level k to the level k+4 through the
relation 16 = 9 + 4 +3x1....So, it is easy to find out quickly the solutions
between 4 and 140. The scarcity reappears when we reach k=140 because we can
use mainly 1, 4 or 9 and the number of possibilities is decreasing
rapidly.Here are the solutions starting from 150:
150 = 147x1 + 2x9 + 1X4
151 = 149X1 + 1X16 + 1X4
152 = 148X1 + 1X9  + 3X4
153 = 151X1 + 2X9
154 = 149X1 + 5X4
155 = 152X1 + 1X9 + 2X4

156 is the first integer for which 169 is not the sum of k nonzero squares.
Indeed, the sole squares which can be used are 1, 4 and 9. So, we have the 2
following equations:
 a + b + c = 156
 a + 4b +9c = 169
where a,b,c are respectively the number of squares 1, 4 and 9.
We infer 3b + 8c = 13
For the possible values of c:0 or 1, there is no solution for b.

 I am not sure to have had a clear understanding of the following
questions,particularly the 2 last ones.  

2)Here is the solution that I propose, corresponding to my comprehension of
the question.
In order to simplify the presentation, let assume that a,b,c,.. represents
the sum: a^2 + b^2 + c^2 +....
For each k from 1 to 10, the first integers are respectively:
k=1  1
k=2  25 = 5^2 = 3,4
k=3  169 = 13^2 = 5,12 = 3,4,12
k=4  7 225 = 85^2 = 13,84 = 5,12,84 = 3,4,12,84
k=5  24 649 = 157^2 = 85,132 = 13,84,132 = etc...
k=6  52 441 = 229^2 = 60,221 = 60,85,204= 13,60,84,204 = etc..
k=7  7 123 561 = 2669^2 = 1445,2244 = 221,1428, 2244 = 85,204,1428, 2244 =
etc..
k=8 159 997 201 = 12649^2 = 2669,12 180 = 1445, 2244, 12180 = etc..
k=9 3 302 685 961 = 57469^2 = 12649, 56100 = 2669,12180,56100 = etc..
k=10  27 882 654 361 = 166981^2 = 57469,156780 = 12649,56100,156780 = etc

To go from the rank k with the solution X(k) to the rank k+1, we look after a
and b integers such as a^2 - b^2 = X(k). If a and b exist, therefore X(k+1) =
a^2. As X(k) is always odd, there is at minimum one solution :
a = (X(k) +1 )/2 and b = (X(k) - 1)/2. If we search the lowest integer, we
express X(k) as a product of prime factors and we retain the 2 odd factors F1
and F2 with F1>F2,the one the closest to the other. So 
a = (F1+F2)/2 and b = (F1-F2)/2. But the branch giving the required numbers
in the global arborescence is not unique (ex k=6 is infered from a second
branch of k=5 )  .

3) In the interval 1 to 100, 25 and 100 would be the sole solutions
corresponding to k=2 which is a maximum.

4) 100 would be the integer which can be decomposed into the most different
sums if squares.When we go from the integer k to the integer k+1, we add 1
which is a square. So the number of decompositions is increasing with k.

The solution to the first problem, as received from the Macalaster mailing list:
--------------------------
Problem 841 Solution Notes
--------------------------

[Added 9/23:]
This is somewhat repetitive, but to rephrase the main theorem relevant to the
sum of squares question (from GrosswaldÕs book): one can say that the smallest
positive integer k for which n is NOT a sum of k nonzero squares is either 1,
2, 3, or n - 13. The stated problem is the first time the n - 13 case occurs.

[Original answer 9/16:]
Herb Wilf (Univ. of Pennsylvania) showed how the problem can be 
elegantly solved using polynomials. His Mathematica code 
follows. He starts with x + x^4 + x^9 + ... + x^169 and forms 
powers of this polynomial, always truncating at the x^169 term. 
The kth power indicates, by virtue of its coefficients, which 
integers are sums of k nonzero squares.

John Guilford (Hewlett-Packard, Everett, Washington) did a 
quite similar thing in C, as did Vahe Poladian, a student at 
Macalester. The speed of Guilford's program is impressive as, 
when it is optimized, it solves the problem as stated in a 
small fraction of a second. John Hamilton (Kodak, Rochester, 
N.Y.) also obtained the answer.



(* Wilf's Mathematica implementation; slower than C, but 
elegant in its use of polynomial arithmetic *)


HWSoln[m_] := Module[{f, rr},
 f =  Sum[x^(j^2), {j, Floor[Sqrt[m]]}];
 Clear[ff];
 ff[1] = f;
 ff[r_] := ff[r] = Sign[Take[
   CoefficientList[Expand[f * ff[r-1]], x], m+1]].
      (x ^ Range[0, m]);
 First[Select[Range[m], Coefficient[ff[#], x, m] == 0 &,1]]]

HWSoln[169]
156


Herb noticed some interesting patterns when one looks at the 
number of integers <= 169 that are representable as a sum of k 
nonzero squares. Here is the data, easily obtained from the 
previous program by letting x -> 1 in the polynomials as they 
are built up. Note that, after k = 7, the number of integers 
that are k-representable decreases by exactly 1 until 156 which 
is the only integer representable as a sum of 156 squares. To 
quote Herb: "What's going on?"

The data:

       Number of integers less
       than 169 that are a sum
  k    of k nonzero squares
 
  2       58
  3      119
  4      152
  5      157
 
  6      157
  7      156
  8      155
  9      154
 10      153
 11      152
 12      151
 13      150
 14      149
 15      148
 16      147
 17      146
 18      145
 19      144
 20      143
 21      142
 22      141
 23      140
 24      139
 25      138
 26      137
 27      136
 28      135
 29      134
 30      133
 31      132
 32      131
 33      130
 34      129
 35      128
 36      127
 37      126
 38      125
 39      124
 40      123
 41      122
 42      121
 43      120
 44      119
 45      118
 46      117
 47      116
 48      115
 49      114
 50      113
 51      112
 52      111
 53      110
 54      109
 55      108
 56      107
 57      106
 58      105
 59      104
 60      103
 61      102
 62      101
 63      100
 64       99
 65       98
 66       97
 67       96
 68       95
 69       94
 70       93
 71       92
 72       91
 73       90
 74       89
 75       88
 76       87
 77       86
 78       85
 79       84
 80       83
 81       82
 82       81
 83       80
 84       79
 85       78
 86       77
 87       76
 88       75
 89       74
 90       73
 91       72
 92       71
 93       70
 94       69
 95       68
 96       67
 97       66
 98       65
 99       64
100       63
101       62
102       61
103       60
104       59
105       58
106       57
107       56
108       55
109       54
110       53
111       52
112       51
113       50
114       49
115       48
116       47
117       46
118       45
119       44
120       43
121       42
122       41
123       40
124       39
125       38
126       37
127       36
128       35
129       34
130       33
131       32
132       31
133       30
134       29
135       28
136       27
137       26
138       25
139       24
140       23
141       22
142       21
143       20
144       19
145       18
146       17
147       16
148       15
149       14
150       13
151       12
152       11
153       10
154        9
155        8
156        7
  

  
And here is another data set, computed by Vahe Poladian. Note 
that the least k for which n is not a sum of k nonzero squares 
seems to be either 1 (the nonsquares), 2, 3, or a very large 
number that, empirically, seems asymptotic to n. Some theorems 
in Grosswald's book (chapter 6) explain why 4 never occurs on 
this list, and also characterize the occurrences of 2 and 3. 
For example, the 2's occur precisely for those squares that are 
not divisible by any primes congruent to 1 (mod 4) and for 
which the power of 2 that divides them is even.

These results are quite striking. It seems as if whenever nis a 
sum of 1, 2, and 3 nonzero squares, then it is also a sum of
4, 5, 6, 7,.......N where N is very close to n.


 n      n^2    Least k s.t n is not
               a sum of k nonzero squares

 2       4      2
 3       9      2
 4      16      2
 5      25      3
 6      36      2
 7      49      2
 8      64      2
 9      81      2
10     100      3
11     121      2
12     144      2
13     169    156
14     196      2
15     225    212
16     256      2
17     289    276
18     324      2
19     361      2
20     400      3
21     441      2
22     484      2
23     529      2
24     576      2
25     625    612
26     676    663
27     729      2
28     784      2
29     841    828
30     900    887
31     961      2
32    1024      2
33    1089      2
34    1156   1143
35    1225   1212
36    1296      2
37    1369   1356
38    1444      2
39    1521   1508
40    1600      3
41    1681   1668
42    1764      2
43    1849      2
44    1936      2
45    2025   2012
46    2116      2
47    2209      2
48    2304      2
49    2401      2
50    2500   2487
51    2601   2588
52    2704   2691
53    2809   2796
54    2916      2
55    3025   3012
56    3136      2
57    3249      2
58    3364   3351
59    3481      2
60    3600   3587
61    3721   3708
62    3844      2
63    3969      2
64    4096      2
65    4225   4212
66    4356      2
67    4489      2
68    4624   4611
69    4761      2
70    4900   4887
71    5041      2
72    5184      2
73    5329   5316
74    5476   5463

Mail to Ken