Исполнитель Стив преобразует число, записанное на экране.
У исполнителя есть три команды, которым присвоены номера:
Прибавить 4,
Прибавить 5,
Умножить на 2.
Первая команда увеличивает число на экране на 4, вторая увеличивает на 5, третья увеличивает число на экране в 2 раза. Программа для Стива — это последовательность команд.
Сколько существует программ, для которых при исходном числе 3 результатом является число 23 и при этом траектория вычислений содержит число 11, но не содержит число 13 и 18? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 123 при исходном числе 7 траектория будет состоять из чисел 11, 16, 32.
Составим фомулы для решения этой задачи:
\(R(n) = R(n-4) + R(n-5)\) — если число не делится на 2.
\(R(n) = R(n-4) + R(n-5) + R(n:2)\) — если число делится на 2.
Заметим, что число 3 мы получаем одним способом — пустой программой. Числа 4, 5 мы получить не можем данными командами. Заполним таблицу:
\[\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c} \hline \text{3} & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\ \hline \text{1} & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 2 & 0 & 0 & 0 & 2 & 2 & 0 & 0 & 2 & 4 & 2 & 2 & 2 \\ \hline \end{array}\]
Ответ: 2