All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Numbers
Sums of Squares (Posted on 2005-02-21) Difficulty: 4 of 5
Some integers cannot be written as a sum of distinct positive squares. Does there exist a largest such integer? If so, find it.

  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.

Comments: ( You must be logged in to post comments.)
  Subject Author Date
AnswerK Sengupta2008-03-21 15:01:57
re: solutionDavid Shin2005-03-01 19:14:31
SolutionsolutionTom2005-03-01 04:03:39
re: researched (spoiler)Richard2005-02-22 17:22:39
re: meowDavid Shin2005-02-22 16:00:26
QuestionmeowRex2005-02-22 14:43:43
Solutionresearched (spoiler)Charlie2005-02-22 14:04:09
questionSachin2005-02-22 06:46:16
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (7)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2018 by Animus Pactum Consulting. All rights reserved. Privacy Information