Sums of Squares (Posted on 2005-02-21)

	Submitted by David Shin
Rating: 3.2857 (7 votes)
Solution:	(Hide)
The answer is yes. The largest such integer is 128. To see why, we first prove a lemma. Lemma. Suppose n is a positive integer, and every integer from n+1 to 4n+35 (inclusive) can be written as a sum of distinct positive squares. Then every integer larger than n can be written as a sum of distinct positive squares. Proof. Suppose not, and let k be the least counterexample. By hypothesis, k>=4n+36. Write k in the form k=4q+r, with 0<r<3, and note that n+9<=q<k. We now consider the four possible values for 4. Suppose first that r=0. By the minimality of k, q can be written as a sum of distinct positive squares; say q=a²+b²+...+z². But then k=4q=(2a)²+(2b)²+...+(2z)², contradicting the assumption that k cannot be written as a sum of distinct positive squares. If r=1 then similar reasoning leads to k=4q+1=(2a)²+(2b)²+...+(2z)²+1, which is again a sum of distinct positive squares. If r=2 then k=4q+2=4(q-2)+10. Since n+7<=q-2<k and k was chosen to be minimal, q-2 can be written as a sum of distinct positive squares; say q-2=a²+b²+...+z². Then k=4(q-2)+10=(2a)²+(2b)²+...+(2z)²+1+9, which is another sum of distinct positive squares. Finally, if r=3 then k=4q+3=4(q-8)+1+9+25, and similar reasoning shows that this is a sum of distinct positive squares. This completes the proof of the lemma. To complete the proof, simply write a computer program that verifies that 128 cannot be written as the sum of distinct squares and that all the integers from 128+1 to 4*128+35 (inclusive) can.

	Subject	Author	Date
	Answer	K Sengupta	2008-03-21 15:01:57
	re: solution	David Shin	2005-03-01 19:14:31
	solution	Tom	2005-03-01 04:03:39
	re: researched (spoiler)	Richard	2005-02-22 17:22:39
	re: meow	David Shin	2005-02-22 16:00:26
	meow	Rex	2005-02-22 14:43:43
	researched (spoiler)	Charlie	2005-02-22 14:04:09
	question	Sachin	2005-02-22 06:46:16