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

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

— если число не делится ни на 2, ни на 3.

— если число делится на 2, но не делится на 3.

— если число делится на 3, но не делится на 2.

— если число делится на 2 и на 3.

Заполним таблицу по данным формулам до 8:

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

Аналогично . Продолжим заполнять таблицу:

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

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

Решение 2

def f(c,m):
    if c > m or c == 9 or c == 24 or c == 32:
        return 0
    if c == m:
        return 1
    return f(c*2,m)+f(c+1,m)+f(c*3,m)

print(f(1,38))