Подсчитав сумму 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 возвращает три правильных значения, изначение 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, посчитав ее цифры, затем взяв число цифр в n-й степени 9 раз 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 ГГц 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
Так что я просто поставил чек на лен списка.