在数字和与produ相同的范围内对数字进行计数

Question

我有一个大范围的数字（从10^5到10^6），我需要计算所有的数字，这些数字的总和等于乘积。在

例如，111126

• 1+1+1+1+2+6=12
• 1*1*1*1*2*6=12

我试过使用下面的代码，它工作得很好，但是非常慢，因为数字范围很大。在

result = 0

for num in range(x, y):
    num_str = str(num)
    summation = 0
    product = 1
    for j in range(len(num_str)):
        summation += int(num_str[j])
        product *= int(num_str[j])
        if j == len(num_str) - 1:
            if summation == product:
                result += 1
print(result)

有没有办法不用循环数数这些数字？如果没有，如何让它跑得更快？在

Answer 1

你根本不需要强行这么做，因为你可以大大限制你的搜索。在

• 任何带有0的数字都将导致乘积为0，而总和将大于等于0。忽略这些数字。
• 顺序无关紧要。1 + 2的和与2 + 1相同，同样适用于它们的乘积。在

最好将注意力集中在具有相等或递增位数的数字上，如果这些数字和乘积的值相同，则对这些数字进行所有唯一的排列。在

要生成候选编号，只有1287个排列，替换范围为1到9的5位数字：

>>> import itertools
>>> len(list(itertools.combinations_with_replacement(range(1, 10), 5)))
1287

搜索空间要小得多：

^{pr2}$

这在很短的时间内就产生了40个结果：

>>> from itertools import combinations_with_replacement, permutations
>>> from operator import mul
>>> from functools import reduce
>>> results = set()
>>> for digits in combinations_with_replacement(range(1, 10), 5):
...     if sum(digits) == reduce(mul, digits):
...         results.update(int(''.join(map(str, p))) for p in permutations(digits))
... 
>>> len(results)
40
>>> for result in sorted(results):
...     print(result)
... 
11125
11133
11152
11215
11222
11251
11313
11331
11512
11521
12115
12122
12151
12212
12221
12511
13113
13131
13311
15112
15121
15211
21115
21122
21151
21212
21221
21511
22112
22121
22211
25111
31113
31131
31311
33111
51112
51121
51211
52111

搜索范围可能会进一步缩小；例如，使用更多的mathematical observations可以缩小对那些至少有21位数的数字的搜索，但是上面的搜索已经相当快了。在

Answer 2

加速循环的常用方法是将其更改为numpy数组，并执行数组操作而不是循环。所以，如果你把你的数字输入一个2D numpy数组，然后做一个数组操作，比如a==B，然后在新数组中计算真值，通常会快得多。在

也许还有比暴力更好的方法。我不清楚您的范围，因为您给出的示例超出了您给出的范围，但是您可以看到最大和是5x9=45。你可以立即删除所有素数大于10的素数。在

例如，您可以遍历5个数的所有可能乘积，例如1<；=b<；=c<；=d<；=9和abed<；=45。当你找到一个解决方案时，只需计算出你找到的另一个类似的解决方案的数量。在