求2^1000的各位数字之和

wayne · 发表于 2009-3-17 09:24:13

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

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

×

如题，求$2^1000$的各位数字之和。我总感觉暗藏着什么好的算法，可就是思维堵住了，大伙帮帮我吧

gxqcn · 发表于 2009-3-17 09:45:47

答案是 1366 似乎没有什么捷径。

wayne · 发表于 2009-3-17 09:59:12

设10^n为a_n，则任何数都是a_i的线性和，可否通过某种递归的特性将2^1000表达成a_i的线性和，最终令所有的a_i为l，从而得解？

无心人 · 发表于 2009-3-17 11:40:52

没有，因为数字和仅和数字相关只要数字参与别的运算，即改变且无任何规律

无心人 · 发表于 2009-3-17 11:42:40

Prelude Char> let digitsSum n = sum [ord(c) - ord('0') | c <- show n] Prelude Char> digitsSum (2^10000) 13561 Prelude Char> digitsSum (2^1000) 1366

wayne · 发表于 2009-3-17 11:48:07

原帖由 无心人 于 2009-3-17 11:40 发表没有，因为数字和仅和数字相关只要数字参与别的运算，即改变且无任何规律

你好像很确信没有啊，这是project euler 上的第16题，就这样brute force，好像不是它的风格

wayne · 发表于 2009-3-17 11:50:19

原帖由 无心人 于 2009-3-17 11:42 发表 Prelude Char> let digitsSum n = sum [ord(c) - ord('0') | c digitsSum (2^10000) 13561 Prelude Char> digitsSum (2^1000) 1366

能问一下你的haskell用的是哪个外壳吗，好象不是winhugs

无心人 · 发表于 2009-3-17 11:53:57

GHCi

无心人 · 发表于 2009-3-17 11:55:20

我想当然的，哈哈有算法，请指教啦

litaoye · 发表于 2009-3-17 14:25:20

是选择题?还是填空题? 填空的话没想出什么好的办法,选择的话,可以用mod 9判断一下!

账号		自动登录	找回密码
密码			欢迎注册

[提问] 求2^1000的各位数字之和

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