平方数数字和

无心人

我想，做这个题目 用HugeCalc不如单纯的支持 64位整数的C快 另外，暴力搜索到10^16是否合适？？？？

gxqcn

赞同楼上观点。

mathe

原帖由 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得出类似规律，从而得到另外一些数也存在平方数数字和为这些数字。 不过还不能覆盖所有的自然数。如果能够在找出一些有规律的数，就可能可以证明题目中的猜想。

mathe

原帖由 无心人 于 2008-7-10 08:13 发表 我想，做这个题目 用HugeCalc不如单纯的支持 64位整数的C快 另外，暴力搜索到10^16是否合适？？？？

平方数的题目比较合适。素数的题目有难度，这么大范围的素数不好求呀。

无心人

或者使用反向递归法从最小可能向上递归 首先固定首位，再考虑末位 末位只能是1，4，5，6，9 而最大位数=(s - 2) 最小位数=(s-10)/9

无心人

刚考虑了 每秒最低速度能达到100万 最大速度估计在1000万

无心人

或者说 如果编码精细的话 最多一个小时的运算时间 最少可能是10分钟 可惜我一会要出门 呵呵 本来有兴趣作的

gxqcn

回复 24# mathe 的帖子 可以通过HugeCalc得到素数（32位下的可分段获取），而后转换成常规类型， 至于统计数字之和，可以分成两部分： 前部分是大于32bit时必须用UINT64，而后的仅用UINT32即可。 要是有64bit的HugeCalc推出就不存在上述问题了。

无心人

对小于等于16*9的可以考虑暴力搜索 很大的，就考虑25#的方法吧

kofeffect

原帖由 mathe 于 2008-7-10 08:11 发表 C/C++写的代码？要运行多长时间？

C代码（我的代码都不会优化，不好！） 前面的时间还好 要算到下面这个就耗了挺长时间， n sum a(n) 42 64 19999999 下一个不知何时出来，俺关机了