Sums of Square Numbers

〇〇

http://www.puzzleup.com/2010/puzzle/?221 我的朋友用程序验证好像是128，能否有严格证明？No: 03 July 28, 2010 Sums of Square Numbers Which is the smallest number that can be expressed as the sum of six different square numbers, but cannot be expressed as the sum of five different square numbers? (Square numbers: 0, 1, 4, 9, 16, 25, ...) [ You need to be a member of this site before you can submit an answer ] today's bonus: 0 points answers: # 166 popularity: 44.8 % difficulty: 23.9 %

northwolves

104吧 104= 1^2+ 2^2+ 3^2 +4^2+ 5^2+ 7 ^2 表示不成5个数的

northwolves

下一个是124，136，188

〇〇

我把题目贴错了，应该是 No: 04 August 04, 2010 Impossible Square Sum What is the largest number that cannot be expressed as a sum of different square numbers? [ You can answer this problem starting from Thursday at 11:00 (GMT) ] today's bonus: -- points answers: # 0 popularity: 31.3 % difficulty: 31.3 %

mathe

并最大不能表示成多少个平方的和？ 任意多个？

mathe

24应该是最大，这是计算的结果，余下的就是证明了:

2. foosquare(n)=
3. {
4. local(v,s,r);
5. v=vector(n*n);
6. v[1]=1;
7. for(u=2,n,
8. s=u*u;
9. for(h=1,n*n-s,
10. if(v[h]==1,v[s+h]=1)
11. );
12. v[s]=1
13. );
14. r=0;
15. for(u=1,n*n,
16. if(v[u]==0,r=u)
17. );
18. r
19. }

复制代码

mathe

证明很简单，通过检验可以发现400以内只有9个数{2, 3, 6, 7, 8, 11, 12, 15, 24}不能写成多个平方数之和 假设我们已经知道对于1和$n^2$之间只有上面9个不能写成不同平方数之和($n>=20$) 于是对于k=n+1,$k^2$和$(k+1)^2$之间的所有数除了$k^2+t$其中t在上面的9个以外都可以写成不同平方数之和。 而又因为$k^2+t-(k-1)^2=2k+t+1$,其中$45<=2k+t+1=2n+t-1<=2n+23<(n-1)^2$ 由归纳假设知道$k^2+t-n^2$可以表示成不同的平方数之和，而且每个平方数不超过$(n-1)^2$ 所以$k^2+t$可以表示成不同平方数之和

northwolves

证明很简单，通过检验可以发现400以内只有9个数{2, 3, 6, 7, 8, 11, 12, 15, 24}不能写成多个平方数之和 假设我们已经知道对于1和$n^2$之间只有上面9个不能写成不同平方数之和($n>=20$) 于是对于k=n+1,$k^2$和$(k+ ... mathe 发表于 2010-8-12 08:43

Mathe 不对吧，我测试了一下，200以内有31个数不能写成不同平方数之和：2, 3, 6, 7, 8, 11, 12, 15, 18, 19, 22, 23, 24, 27, 28, 31, 32, 33, 43, 44, 47, 48, 60, 67, 72, 76, 92, 96, 108, 112, 128

northwolves

There are only 31 numbers that cannot be expressed as the sum of distinct squares: 2, 3, 6, 7, 8, 11, 12, 15, 18, 19, 22, 23, 24, 27, 28, 31, 32, 33, 43, 44, 47, 48, 60, 67, 72, 76, 92, 96, 108, 112, 128 (Sloane's A001422; Guy 1994; Savin 2000). http://mathworld.wolfram.com/SquareNumber.html

northwolves

这样证明也可以吧： 记M(n)=[0, 255] +(16n)² n=0,M(0)的元素只有上面31个不能写成不同平方数之和 假设n<=k时，M(k)的元素只有上面31个不能写成不同平方数之和 M(k+1)=[0, 255] +(16(k+1))²=[0, 255] +(16k)² +32k+256 ......