找回密码
 欢迎注册
查看: 12624|回复: 11

[讨论] Sums of Square Numbers

[复制链接]
发表于 2010-8-11 20:52:17 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
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 %
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-8-11 22:44:10 | 显示全部楼层
104吧
104= 1^2+  2^2+  3^2  +4^2+  5^2+  7 ^2
表示不成5个数的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-8-11 22:50:27 | 显示全部楼层
下一个是124,136,188
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-8-12 05:33:38 | 显示全部楼层
我把题目贴错了,应该是
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 %
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-8-12 08:16:37 | 显示全部楼层
并最大不能表示成多少个平方的和?
任意多个?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-8-12 08:32:10 | 显示全部楼层
24应该是最大,这是计算的结果,余下的就是证明了:

  1. foosquare(n)=
  2. {
  3.     local(v,s,r);
  4.     v=vector(n*n);
  5.     v[1]=1;
  6.     for(u=2,n,
  7.         s=u*u;
  8.         for(h=1,n*n-s,
  9.            if(v[h]==1,v[s+h]=1)
  10.         );
  11.         v[s]=1
  12.     );
  13.     r=0;
  14.     for(u=1,n*n,
  15.         if(v[u]==0,r=u)
  16.     );
  17.     r
  18. }
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-8-12 08:43:54 | 显示全部楼层
证明很简单,通过检验可以发现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$可以表示成不同平方数之和
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-8-12 20:40:55 | 显示全部楼层
证明很简单,通过检验可以发现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
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-8-12 20:47:21 | 显示全部楼层
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
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-8-12 21:56:57 | 显示全部楼层
这样证明也可以吧:

记M(n)=[0,  255] +(16n)2
n=0,M(0)的元素只有上面31个不能写成不同平方数之和
假设n<=k时,M(k)的元素只有上面31个不能写成不同平方数之和
M(k+1)=[0,  255] +(16(k+1))2=[0,  255] +(16k)2 +32k+256
......
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 03:20 , Processed in 0.046183 second(s), 16 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表