Show that all but finitely many positive integers can be represented as a sum of distinct squares.
Solution
The key idea is to write 29 = 22 + 52, 2.29 = 32 + 72. Now given any positive integer n, write n in binary, so n is a sum of distinct powers of 2. Let r be the sum of the odd powers of 2, and s the sum of the even powers of 2. So n = r + s, and we have r = (2a + 2b + ... ), where 1 ≤ a < b < ... . Similarly, s = (2i + 2j + ... ), where 0 ≤ i < j < ... .
Now 4.29 r = (32 + 72) x 2r = 32( a sum of distinct even powers of 2, all ≥ 4) + 72( a sum of distinct even powers of 2, all >= 4). Similarly, 4.29 s = (22 + 52) x 4s = 22( a sum of distinct even powers of 2, all >= 4) + 52( a sum of distinct even powers of 2, all ≥ 4). Thus 4.29 n = a sum of distinct even squares. For example, if n = 79, we have n = 1 + 2 + 4 + 8 + 64 = (1 + 4 + 64) + (2 + 8), so 4.49 n = (22 + 52)(4 + 16 + 256) + (32 + 72)(4 + 16) = 42 + 82 + 322 + 102 + 202 + 802 + 62 + 122 + 142 + 282.
We can write any integer n as 116q + r with 0 ≤ r < 116. Now r = 12 + (58 + 1)2 + (58.2 + 1)2 + (58.3 + 1)2 + ... + (58(r-1) + 1)2 mod 116 (because (58k + 1)2 = 1 + 116k + 582k2 = 1 mod 116 and there are r squares in the sum). So provided n > K = 12 + (58.1 + 1)2 + ... + (58.114 + 1)2, we can write n = 12 + (58.1 + 1)2 + ... + (58(r-1) + 1)2 + 116k for some non-negative k. Now we are home, because the squares are all odd and distinct, whereas 116k can be written as a sum of distinct even squares.
Note that several small integers cannot be written as a sum of distinct squares. For example, 2, 3, 6, 7, 8, 11, 12, 15, 18, 19, 22, 23, 24, 27, 28, 31.
© John Scholes
jscholes@kalva.demon.co.uk
10 Oct 2002