23.04 Количество программ из A в B где траектория вычислений НЕ содержит число(-а)

Пусть — количество программ, которое число 1 преобразует в число . Тогда верно следующее утверждение:

Заполним таблицу по данной формуле до 12:

Так как по условию сказано, что траектория не должна содержать число 13, значит . Продолжим заполнять таблицу:

Аналогично . Заполним таблицу до конца:

Отсюда получаем ответ — 796.

Рекурсия:

def f(c,m):
    if c > m or c == 13 or c == 19:
        return 0
    if c == m:
        return 1
    return f(c+2,m)+f(c+3,m)+f(c+5,m)

print(f(1,25))