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

Question

我正在尝试完成Project Euler 问题 #30，我决定根据已知答案验证我的代码。基本上问题是这样的：找出所有可以写成它们数字的五次方之和的数字的总和。这是我试图用python证明的已知答案：1634 = 1^4 + 6^4 + 3^4 + 4^48208 = 8^4 + 2^4 + 0^4 + 8^49474 = 9^4 + 4^4 + 7^4 + 4^4由于 1 = 1^4 不是总和，因此不包括在内。这些数字的总和是 1634 + 8208 + 9474 = 19316。当我运行我的代码时，我得到所有三个加起来为 19316 的值，太棒了！但是在这些值中有一个不正确的值：6688这是我的代码：i=1answer = []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:

    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 次方乘以9的 n 次方的位数来找到这样的点。如果这会创建一个具有更多位数的数字，请继续操作，直到位数不再变化。

本着同样的精神，你就可以开始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 在不到半秒的时间内产生所需的输出。

Answer 2

这里固定：

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 and len(list) == 4:

           print(sum(list))

           answer.append(sum(list))

我发现的错误：

6^4+6^4+8^4 = 6688

所以我只是检查了列表的 len。