python - 计算每个数字的4次方之和，为什么会得到错误的结果？

Question

我正在尝试完成 Project Euler question #30 ，我决定根据已知答案验证我的代码。基本上问题是这样的:

Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

这是我试图用 python 证明的已知答案:

1634 = 1^4 + 6^4 + 3^4 + 4^4
8208 = 8^4 + 2^4 + 0^4 + 8^4
9474 = 9^4 + 4^4 + 7^4 + 4^4

As 1 = 1^4 is not a sum it is not included.

The sum of these numbers is 1634 + 8208 + 9474 = 19316.

当我运行我的代码时，我得到了所有三个值，它们加起来等于 19316，太棒了! 但是在这些值中有一个不正确的值:6688

这是我的代码:

i=1
answer = []

while True:
    list = []
    i=i+1
    digits = [int(x) for x in str(i)]

    for x in digits:
        a = x**4
        list.append(a)

        if sum(list) == i:
            print(sum(list))
            answer.append(sum(list))

list 的总和返回三个正确的值，以及值 6688。任何人都可以发现我遗漏的东西吗？

Answer 1

您检查总和太早了。您检查数字中每个数字的匹配总和，以及 6 ^ 4 + 6 ^ 4 + 8 ^ 4是6688 .这是数字的三位，而不是全部四位。

移动您的 sum()测试 你的 for循环:

for x in digits:
    a = x**4
    list.append(a)

if sum(list) == i:
    print(sum(list))
    answer.append(sum(list))

充其量你可以在总和已经超过目标时提前丢弃一个数字:

digitsum = 0
for d in digits:
    digitsum += d ** 4
    if digitsum > i:
        break
else:
    if digitsum == i:
        answer.append(i)

但我不想在这里费心，只是使用生成器表达式来组合确定数字、将它们提升到 4 次方并求和:

if sum(int(d) ** 4 for d in str(i)) == i:
    answer.append(i) 

您还没有定义上限，即数字始终大于其数字总和的点，您需要停止递增 i .对于 n 次方的和，您可以通过取 9 ^ n，计算其位数，然后取 9 的 n 次方的位数 乘以 的 n 次方来找到这样的点9.如果这创建了一个位数更多的数字，请继续，直到位数不再改变。

同理，你可以开始i在 max(10, 1 + 2 ** n) ，因为您可以从数字中得出的最小总和将使用单个 2数字加最小数1和 0你可以逃脱的数字，并且在任何大于 1 的幂时，除 1 和 0 之外的数字的幂总是大于数字值本身，你不能使用 i = 1 :

def determine_bounds(n):
    """Given a power n > 1, return the lower and upper bounds in which to search"""
    nine_power, digit_count = 9 ** n, 1
    while True:
        upper = digit_count * nine_power
        new_count = len(str(upper))
        if new_count == digit_count:
            return max(10, 2 ** n), upper
        digit_count = new_count

如果将上述函数与 range(*<expression>) 结合使用可变长度参数传递给 range() , 你可以使用 for循环:

for i in range(*determine_bounds(4)):
    # ...

您可以确定一个数是否等于其数位的给定幂次之和 n在函数中:

def is_digit_power_sum(i, n):
    return sum(int(d) ** n for d in str(i)) == i

然后你可以将所有内容放入一个列表理解中:

>>> n = 4
>>> [i for i in range(*determine_bounds(n)) if is_digit_power_sum(i, n)]
[1634, 8208, 9474]
>>> n = 5
>>> [i for i in range(*determine_bounds(n)) if is_digit_power_sum(i, n)]
[4150, 4151, 54748, 92727, 93084, 194979]

is_digit_power_sum()可以从权力的缓存中受益；添加缓存会使函数对于 4 位输入的速度提高两倍以上:

def is_digit_power_sum(i, n, _cache={}):
    try:
        powers = _cache[n]
    except KeyError:
        powers = _cache[n] = {str(d): d ** n for d in range(10)}
    return sum(powers[d] for d in str(i)) == i

当然，问题的解决方案是数字的总和:

n = 5
answer = sum(i for i in range(*determine_bounds(n)) if is_digit_power_sum(i, n))
print(answer)

在我的 2.9 GHz Intel Core i7 MacBook Pro 上使用 Python 3.8.0a3 在半秒内产生所需的输出。