数字求和！

Question

你好，我在尝试解决这个问题：

假设 P(n) 是 2^n 的数字之和。
比如说：
2^15 = 32768，而它的数字之和是 3 + 2 + 7 + 6 + 8 = 26，所以 P(15)=26。
计算从 n=1 到 10000 的 P(n) 的总和。

这是我的python 代码，结果给出的答案是67783431，但评审似乎不同意这个结果：

def P(n):
    n = int(1<<n)
    S = 0
    while n != 0:
        S += (n%10)
        n /= 10
    return S

Sum = 0
for i in range(1,10001):
    Sum += P(i)
else:
    print(Sum)

有没有人能告诉我我这个方法哪里出错了？如果有人能给我指个数学上的解决方案，我会很感激。

Answer 1

你的解决方案运行起来花了很长时间（总之超过了一分钟）。评审者对解决方案的运行时间有没有设定限制呢？

另外，如果你使用的是Python 3，那么除法运算符（/=）总是会得到一个浮点数的结果。在Python 2中，如果输入是整数，结果会被截断成整数。

实际上，在Python 3中我遇到了溢出错误：

Traceback (most recent call last):
  File "<stdin>", line 2, in <module>
  File "<stdin>", line 6, in P
OverflowError: int/int too large for a float

Answer 2

一个更优雅的解决方案，从函数式编程的角度来看，可能是：

>>> P = lambda n: sum(map(int, str(1 << n)))
>>> sum(P(i) for i in xrange(10001))
67783432

（注意，这段代码计算的是从0到10000的P(i)的总和。）

Answer 3

如果你看了评论，就会发现这个网站的拥有者或者问题的维护者真是个傻瓜。

他本来想说的是“从0到10000”，而不是“从1到10000”，但显然这个问题不能被编辑，或者维护者不想去改。

这个总和多了1，因为 1<<0 的结果是1，这就让总和多加了1。

试着提交67783432吧。

注意: 我知道叫网站的拥有者或维护者傻瓜可能听起来有点过分，但在一个关于“数学”的网站上发布内容时，准确性是非常重要的。拥有这样一个网站却没有能力或者要求去修正错误的问题，感觉有点傻。