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

Для подсчёта количества программ используем рекурсивную функцию. Аргументы функции обозначают количество способов преобразовать число в число при заданных правилах. Если или в процессе получено число , то таких путей нет. Если , найден один способ. Иначе программа может продолжиться тремя командами: , или . Таким образом, + f(a**2, b). Общее количество программ результату вызова функции при и .

# Рекурсивная функция для подсчета количества программ
def f(a, b):
    # Если текущее число больше целевого или равно 11 — пути нет
    if a > b or a == 11:
        return 0
    # Если достигли целевого числа, найден один путь
    if a == b:
        return 1
    # Иначе продолжаем тремя возможными командами:
    # A: a + 1, B: a * 2
    return f(a + 1, b) + f(a * 2, b) + f(a ** 2, b)


# Количество программ от 1 до 35 через 10, без числа 17
print(f(2, 20))