Задание 23. Информатика. Статград 2023-1-1

Исполнитель преобразует число на экране.
У исполнителя есть две команды, которым присвоены номера:

1. Прибавить \(1\)
2. Умножить на \(2\)

Первая команда увеличивает число на экране на \(1\), вторая умножает его на \(2\).
Программа для исполнителя — это последовательность команд. Например, если в начальный момент на экране находится число \(1\), то программа \(212\) последовательно преобразует его в \(2\), \(3\), \(6\).
Сколько существует программ, для которых преобразуют исходное число \(1\) в число \(40\) так, что в процессе выполнения на экране ни разу не появляется цифра \(3\)?

def f(n, target):
    if n == target:
        return 1
    if n > target or '3' in str(n):
        return 0
    return f(n+1, target) + f(2*n, target)

print(f(1, 40))