找回密码
 欢迎注册
楼主: mathe

[擂台] 平方数数字和

[复制链接]
发表于 2008-7-10 08:13:55 | 显示全部楼层
我想,做这个题目
用HugeCalc不如单纯的支持
64位整数的C快

另外,暴力搜索到10^16是否合适????
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-7-10 08:15:23 | 显示全部楼层
赞同楼上观点。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-7-10 08:16:09 | 显示全部楼层
原帖由 gxqcn 于 2008-7-9 10:09 发表
找出一条规律:
  27…7(n个7)88…8(n+1个8)9 是 16…6(n个6)7 的平方。

该规律虽无法保证得到S(15n+19)的下限,但对缩小下限却很有帮助,
因为除了首位2以外,其它都是相对很大的数字。

这个结论还有一个用处是证明了对于15n+19,存在平方数数字和为这么多。
类似,我们还可以通过166..61,166...62,...,166...69得出类似规律,从而得到另外一些数也存在平方数数字和为这些数字。
不过还不能覆盖所有的自然数。如果能够在找出一些有规律的数,就可能可以证明题目中的猜想。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-7-10 08:17:15 | 显示全部楼层
原帖由 无心人 于 2008-7-10 08:13 发表
我想,做这个题目
用HugeCalc不如单纯的支持
64位整数的C快

另外,暴力搜索到10^16是否合适????

平方数的题目比较合适。素数的题目有难度,这么大范围的素数不好求呀。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-7-10 08:17:49 | 显示全部楼层


或者使用反向递归法从最小可能向上递归
首先固定首位,再考虑末位
末位只能是1,4,5,6,9
而最大位数=(s - 2)
最小位数=(s-10)/9
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-7-10 08:19:40 | 显示全部楼层
刚考虑了
每秒最低速度能达到100万
最大速度估计在1000万
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-7-10 08:20:58 | 显示全部楼层
或者说
如果编码精细的话

最多一个小时的运算时间
最少可能是10分钟

可惜我一会要出门
呵呵
本来有兴趣作的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-7-10 08:23:13 | 显示全部楼层
回复 24# mathe 的帖子

可以通过HugeCalc得到素数(32位下的可分段获取),而后转换成常规类型,
至于统计数字之和,可以分成两部分:
前部分是大于32bit时必须用UINT64,而后的仅用UINT32即可。

要是有64bit的HugeCalc推出就不存在上述问题了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-7-10 08:23:24 | 显示全部楼层
对小于等于16*9的可以考虑暴力搜索

很大的,就考虑25#的方法吧
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-7-10 08:27:50 | 显示全部楼层
原帖由 mathe 于 2008-7-10 08:11 发表
C/C++写的代码?要运行多长时间?

C代码(我的代码都不会优化,不好!)
前面的时间还好
要算到下面这个就耗了挺长时间,
n      sum    a(n)
42     64      19999999

下一个不知何时出来,俺关机了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-3-29 04:27 , Processed in 0.046207 second(s), 15 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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