数字之和，属性，求提示

Question

这是一个问题：

有多少个整数满足 0 ≤ n < 10^18，并且这些整数 n 的数字之和等于 137n 的数字之和？

这个解决方案效率非常低。我漏掉了什么呢？

#!/usr/bin/env python
#coding: utf-8

import time
from timestrings import *

start = time.clock()

maxpower = 18
count = 0

for i in range(0, 10 ** maxpower - 1):
    if i % 9 == 0:
        result1 = list(str(i))
        result2 = list(str(137 * i))
        sum1 = 0
        for j in result1:
            sum1 += int(j)
        sum2 = 0
        for j in result2:
            sum2 += int(j)
        if sum1 == sum2:
            print (i, sum1)
            count += 1

finish = time.clock()

print ("Project Euler, Project 290")
print ()
print ("Answer:", count)
print ("Time:", stringifytime(finish - start))

Answer 1

我用这种暴力破解的Python方法计算7位数，花了我19秒钟：

print sum(sum(map(int, str(n))) == sum(map(int, str(137 * n)))
          for n in xrange(0, 10 ** 7, 9)) 

在同一台机器上，单核处理器，使用相同的Python解释器和代码，计算18位数大约需要3170年（这是题目要求的）。

可以参考dgg32的回答，那里有更快的计算方法的灵感。

Answer 2

你正在尝试用暴力破解的方法来解决一个Project Euler的问题。这种方法可能对前几个问题有效，但对于大多数问题，你需要考虑更聪明的解决办法。

因为我觉得不应该给出针对这个问题的具体建议，所以你可以看看这个回答里的一些通用建议。

Answer 3

首先，你要计算，而不是显示结果。

这一点非常重要。你需要找到一种高效的方式来进行计数。正如Jon Bentley在《编程珠玑》中所说：“任何考虑到一个单词所有字母排列的方法都是注定要失败的。”实际上，我在Python中尝试过，当“i”达到10^9时，系统就已经卡住了，消耗了1.5G的内存。更不用说10^18了。这也告诉我们，再次引用Bentley的话，“定义问题大约占了这场战斗的九成。”

要解决这个问题，我认为没有动态规划（dp）是不行的。实际上，大多数那些看起来非常复杂的欧拉问题都需要某种形式的动态规划。动态规划的理论本身比较学术和枯燥，但把动态规划的思想应用到实际问题中去并不难，实际上，实践是有趣且多彩的。

解决这个问题的一种方法是，我们从0-9开始，然后是10-99，再到100-999，依此类推，提取数字的特征，汇总具有相同特征的数字，把它们当作一组来处理，从而节省空间和时间。

观察一下：3 * 137 = 411，13 * 137 = 1781。我们把第一个结果“411”分成两部分：前两位“41”和最后一位“1”。“1”会保留，但“41”部分会被“进位”到后续计算中。我们把“41”称为进位，作为特征的第一个元素。“1”会作为最右边的数字继续参与计算，比如13 * 137、23 * 137、33 * 137或43 * 137。这些乘以3的数字都有一个“3”作为它们的最右边数字，而137*n的最后一位总是1。也就是说，这个“3”和“1”之间的差是+2，我们把这个+2称为“差”，作为特征的第二个元素。

好吧，如果我们要找一个以3结尾的两位数，我们需要找到一个数字“m”，使得

diff_of_digitsum (m, 137*m+carry) = -2 (1)

来抵消我们之前累积的+2差。如果m能做到这一点，那么你知道m * 10 + 3，写在纸上的就是“m3”，就是一个结果。

例如，在我们的例子中，我们尝试数字1。diff_of_digitsum (digit, 137*digit+carry) = diff_of_digitsum (1, 137*1+41) = -15。这不是-2，所以13不是一个结果。

再看看99。9 * 137 = 1233。这个“差”是9 - 3 = +6。“进位”是123。在第二次迭代中，当我们尝试把数字9加到9上，变成99时，我们有diff_of_digitsum (digit, 137*digit+carry) = diff_of_digitsum (9, 137*9+123) = diff_of_digitsum (9, 1356) = -6，这样就抵消了我们多出来的6。所以99是一个结果！

在代码中，我们只需要18次迭代。在第一轮，我们处理单个数字，第二轮处理两位数，然后是三位数……直到我们处理到18位数。在迭代之前，先做一个结构像这样的表：

table[(diff, carry)] = amount_of_numbers_with_the_same_diff_and_carry

然后开始迭代，你需要在进行过程中不断更新表格。如果遇到新的特征，就添加新的条目，并始终更新相同差和进位的数字数量。第一轮，处理单个数字，填充表格：

0: 0 * 137 = 0，差：0；进位：0。table[(0, 0)] = 1

1: 1 * 137 = 137。差：1 - 7 = -6；进位：13。table[(-6, 13)] = 1

2: 2 * 137 = 274。差：2 - 7 = -5；进位：27。table[(-5, 27)] = 1

依此类推。

第二次迭代，处理“10”位数字，我们会遍历数字0-9作为你的“m”，并用它在(1)中查看是否能产生抵消“差”的结果。如果可以，这意味着这个m会使所有相同差和进位的数字数量变成结果。因此是计算而不是显示。然后我们可以用这个数字添加的新信息来计算新的差和进位，就像例子中9的差是6，进位是123，但99的差是9 - 6（来自1356的最后一位）= 3，进位是135，用新信息替换旧表。

最后一点，注意数字0。它在迭代中会出现很多次，不要过度计算，因为0009 = 009 = 09 = 9。如果你使用C++，确保总和使用无符号长整型和那种类型，因为它很大。祝你好运。