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:
Source: Based upon Macalester College Problems of the Week #841.
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.
--------------------------
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