Проект Эйлера № 254: суммы факториалов цифр — это математическая задача с веб-сайта Проекта Эйлера. Постановка задачи: найти сумму всех чисел n таких, что сумма факториалов их цифр равна n.

Вот несколько способов решения этой проблемы, а также примеры кода:

Метод 1: перебор
Самый простой подход — перебрать все числа до заданного предела и вычислить сумму их цифровых факториалов. Если сумма совпадает с самим числом, она добавляется к окончательному результату.

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)
def sum_digit_factorials(n):
    return sum(factorial(int(digit)) for digit in str(n))
def find_sum_of_digit_factorials(limit):
    result = 0
    for n in range(limit):
        if n == sum_digit_factorials(n):
            result += n
    return result
limit = 100000  # Adjust the limit accordingly
sum_of_digit_factorials = find_sum_of_digit_factorials(limit)
print(sum_of_digit_factorials)

Метод 2: мемоизация
Чтобы оптимизировать метод грубой силы, мы можем использовать мемоизацию для хранения факториалов каждой цифры. Это позволяет избежать избыточных вычислений при проверке нескольких чисел.

factorial_cache = {}
def factorial(n):
    if n in factorial_cache:
        return factorial_cache[n]
    if n == 0:
        return 1
    result = n * factorial(n - 1)
    factorial_cache[n] = result
    return result
def sum_digit_factorials(n):
    return sum(factorial(int(digit)) for digit in str(n))
def find_sum_of_digit_factorials(limit):
    result = 0
    for n in range(limit):
        if n == sum_digit_factorials(n):
            result += n
    return result
limit = 100000  # Adjust the limit accordingly
sum_of_digit_factorials = find_sum_of_digit_factorials(limit)
print(sum_of_digit_factorials)

Метод 3: математическое наблюдение
Наблюдая за задачей, мы можем заметить, что сумма факториалов цифр не может превышать определенный предел (например, 9! * 7, как максимальная сумма для 7-значного числа). Мы можем использовать это наблюдение, чтобы уменьшить пространство поиска и повысить производительность.

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)
def sum_digit_factorials(n):
    return sum(factorial(int(digit)) for digit in str(n))
def find_sum_of_digit_factorials(limit):
    result = 0
    for n in range(10, limit):
        if n == sum_digit_factorials(n):
            result += n
    return result
limit = 1000000  # Adjust the limit accordingly
sum_of_digit_factorials = find_sum_of_digit_factorials(limit)
print(sum_of_digit_factorials)