Блог

Я пытаюсь завершить проект 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 . Кто-нибудь может заметить что-то, что я пропустил?

Вы слишком рано проверяете сумму. Вы проверяете соответствие суммы для каждой отдельной цифры в числе, и 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)
  

который выдает требуемый результат менее чем за полсекунды на моем MacBook Pro с процессором Intel Core i7 с частотой 2,9 ГГц, используя Python 3.8.0a3.

Здесь исправлено:

 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 списка.