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

Решение 1 (Рекурсия)

def f(st, fn, exit_number):
    if st == fn:
        return 1
    if st > fn or st == exit_number:
        return 0
    x = f(st + 2, fn, exit_number)
    y = f(st * 3, fn, exit_number)
    z = f(st + st % 2 + 2, fn, exit_number)
    return x + y + z
print(f(1, 15, 13))

Решение 2 (Динамика)

a = [0] * 16 * 3
a[1] = 1
for i in range(1, 15):
    if i != 13:
        a[i + 2] += a[i]
        a[i * 3] += a[i]
        a[i + i % 2 + 2] += a[i]
print(a[15])

Решение 3 (Динамика)

a = [0] * 16
a[1] = 1
# 2 -> 2 + 0 + 2 = 4
# 1 -> 1 + 1 + 2 = 4
for i in range(2, 16):
    a[13] = 0
    a[i] = a[i - 2] + a[i // 3] * (i % 3 == 0) + (a[i - 2] + a[i - 2 - 1]) * (i % 2 == 0)
print(a[15])