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