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

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

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

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

Заметим, что количество программ изменяется только на четных n. Значит следующее число, на котором изменится количество программ — 12. По условию нам дано, что траектория должна содержать число 10, значит — . Далее данное значение не будет меняться, так как тогда траектория не будет проходить через число 10.

В итоге получаем ответ — 7

Решение 2

def f(c,m):
    if c > m:
        return 0
    if c == m:
        return 1
    return f(c*2,m)+f(c+1,m)

print(f(2,10)*f(10,17))