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

Question

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

找出所有可以写成它们数字的五次方之和的数字的总和。

这是我试图用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

由于 1 = 1^4 不是总和，因此不包括在内。

这些数字的总和是 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返回三个正确值的总和，以及 value 6688。有人能发现我错过的东西吗？

Answer 1

你过早地检查总和。您检查数字中每个单独数字的匹配总和，并且6 ^ 4 + 6 ^ 4 + 8 ^ 4是6688。那是三个数字，而不是全部四个数字。将你的sum()测试出你的for循环：for x in digits:&nbsp; &nbsp; a = x**4&nbsp; &nbsp; list.append(a)if sum(list) == i:&nbsp; &nbsp; print(sum(list))&nbsp; &nbsp; answer.append(sum(list))当总和已经超过目标时，您最多可以尽早丢弃一个数字：digitsum = 0for d in digits:&nbsp; &nbsp; digitsum += d ** 4&nbsp; &nbsp; if digitsum > i:&nbsp; &nbsp; &nbsp; &nbsp; breakelse:&nbsp; &nbsp; if digitsum == i:&nbsp; &nbsp; &nbsp; &nbsp; answer.append(i)但我不会在这里打扰，只需使用生成器表达式来组合确定数字，将它们提高到 4 次方，然后求和：if sum(int(d) ** 4 for d in str(i)) == i:&nbsp; &nbsp; answer.append(i)&nbsp;您尚未定义上限，即数字始终大于数字总和并且您需要停止递增的点i。对于 n 次方的总和，您可以通过取 9 ^ n，计算其位数，然后取9的 n 次方乘以9的 n 次方的位数来找到这样的点。如果这会创建一个具有更多位数的数字，请继续操作，直到位数不再变化。本着同样的精神，你就可以开始i在max(10, 1 + 2 ** n)，因为你就可以从数字来最小总和将使用一个单一的2数字加的最小数目1和0数字，你可以逃脱，并在任何功率大于1， 1 和 0 以外的数字的幂总是大于数字值本身，您不能使用i = 1：def determine_bounds(n):&nbsp; &nbsp; """Given a power n > 1, return the lower and upper bounds in which to search"""&nbsp; &nbsp; nine_power, digit_count = 9 ** n, 1&nbsp; &nbsp; while True:&nbsp; &nbsp; &nbsp; &nbsp; upper = digit_count * nine_power&nbsp; &nbsp; &nbsp; &nbsp; new_count = len(str(upper))&nbsp; &nbsp; &nbsp; &nbsp; if new_count == digit_count:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return max(10, 2 ** n), upper&nbsp; &nbsp; &nbsp; &nbsp; digit_count = new_count如果将上述函数与range(*<expression>)传递给的可变长度参数结合起来range()，则可以使用for循环：for i in range(*determine_bounds(4)):&nbsp; &nbsp; # ...您可以n在函数中确定一个数字是否等于其数字的总和到给定的幂：def is_digit_power_sum(i, n):&nbsp; &nbsp; 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={}):&nbsp; &nbsp; try:&nbsp; &nbsp; &nbsp; &nbsp; powers = _cache[n]&nbsp; &nbsp; except KeyError:&nbsp; &nbsp; &nbsp; &nbsp; powers = _cache[n] = {str(d): d ** n for d in range(10)}&nbsp; &nbsp; return sum(powers[d] for d in str(i)) == i当然，问题的解决方案是数字的总和：n = 5answer = 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 在不到半秒的时间内产生所需的输出。

Answer 2

这里固定：i=1answer = []while True:&nbsp; &nbsp; list = []&nbsp; &nbsp; i=i+1&nbsp; &nbsp; digits = [int(x) for x in str(i)]&nbsp; &nbsp; for x in digits:&nbsp; &nbsp; &nbsp; &nbsp; a = x**4&nbsp; &nbsp; &nbsp; &nbsp;list.append(a)&nbsp; &nbsp; &nbsp; &nbsp;if sum(list) == i and len(list) == 4:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;print(sum(list))&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;answer.append(sum(list))我发现的错误：6^4+6^4+8^4 = 6688所以我只是检查了列表的 len。