16.01 Одна функция

Рекурсивное решение

В задаче задан рекурсивный алгоритм, при котором функция в процессе вычислений вызывает сама себя с другими аргументами. Для реализации создаём пользовательскую функцию в Python с помощью . Внутри функции используем условный оператор , чтобы задать ветвление: при ; если и , то ; иначе . Перебираем все , для каждого вычисляем , находим сумму его десятичных цифр , проверяем, является ли простым числом, и считаем количество таких . Для ускорения вычислений удобно кэшировать значения .

from functools import lru_cache

# Кэширование результатов для оптимизации
@lru_cache(None)
def f(n):
    # База рекурсии
    if n <= 1:
        return 1
    # При n > 1 и n кратно 3
    elif n > 1 and n % 3 == 0:
        return f(n - 1) + f(n - 2) + n
    # Иначе
    else:
        return f(n - 2) + 2

# Функция для вычисления суммы цифр
def summa(n):
    dig_sum = 0
    while n > 0:
        dig_sum += (n % 10)
        n //= 10
    return dig_sum

# Проверка на простоту
def is_prime(n):
    if n < 2:
        return False
    # Перебираем до корня
    for j in range(2, int(n ** 0.5) + 1):
        # Если хоть один делитель есть, то число простое
        if n % j == 0:
            return False
    return True

ans = 0
for i in range(1, 1500 + 1):
    # Если сумма цифр простая
    if is_prime(summa(f(i))):
                                                                                                     
                                                                                                     
        # То обновляем счётчик
        ans += 1
print(ans)