计算数字总和与乘积相同的范围内的数字

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

通常加速循环的方法是将它们更改为numpy数组，并进行数组操作而不是循环。因此，如果您将数字放入 2D numpy 数组中，然后执行数组操作（例如 A==B）并计算新数组中的真值，通常会快得多。

可能还有比蛮力更好的方法。我不清楚你的范围，因为你给出的例子超出了你给出的范围，但你可以看到最大和是 5x9 = 45。你可以立即删除任何总和大于 10 的素数。

例如，您可以遍历 5 个数字 a,b,c,d,e 的所有不同可能乘积，使得 1<= b<=c<=d<=e<=9 且 abced<=45。当您找到解决方案时，只需算出其他类似解决方案的数量，这些解决方案是您找到的解决方案的排列。

Answer 2

你根本不需要暴力破解，因为你可以大大限制你的搜索。

任何包含 0 的数字都将导致乘积为 0，而总和将 > 0。忽略此类数字。
数字顺序无关紧要。 1 + 2的和和2 + 1是一样的，他们的乘积也是一样。

然后最好关注具有相等或递增数字的数字，如果这些数字的总和与乘积的值相同，您将采用这些数字的所有唯一排列。

要生成候选号码，只有 1287 个排列，并从 1 到 9 范围内的 5 位数字进行替换：

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

这是一个小得多的搜索 space:

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):
        # add unique permutations of the digits as a new integer
        results.update(int(''.join(map(str, p))) for p in permutations(digits))

for result in sorted(results):
    print(result)

这确实在很短的时间内产生了 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，您可以缩小对至少 2 1 位数字的搜索范围，但上面的搜索速度已经相当快了。

计算数字总和与乘积相同的范围内的数字

Count numbers in range which sum of digits is same as product

python

algorithm

for-loop

range

python-3.x