PDF-версии: 
У исполнителя Калькулятор две команды, которым присвоены номера:
1. прибавь 1
2. умножь на 2
Сколько есть программ, которые число 1 преобразуют в число 16?
Решение. Обозначим R(n) — количество программ, которые преобразуют число 2 в число n. Обозначим t(n) наибольшее кратное 2, не превосходящее n. Заметим, что мы можем получить только числа, кратные 2.
Верны следующие соотношения:
1. Если n не делится на 2, то тогда R(n) = R(t(n)), так как существует единственный способ получения n из t(n) — прибавлением единиц.
2. Пусть n делится на 2. Тогда R(n) = R(n / 2) + R(n − 1)= R(n / 2) + R(n − 2) (если n > 2). При n = 2 R(n)) = 1 (один способ: прибавлением единицы). Поэтому достаточно постепенно вычислить значения R(n) для всех чисел, кратных 2 и не превосходящих 16.
Имеем:
R(2)= 2 = R(3),
R(4)= 2 + 2 = 4 = R(5),
R(6) = 2 + 4 = 6 = R(7),
R(8) = R(4)+R(6) = 4 + 6 = 10 = R(9),
R(10) = R(5) + R(8) = 4 + 10 = 14 = R(11),
R(12) = R(6) + R(10) = 6 + 14 = 20 = R(13),
R(14) = R(7) + R(12) = 6 + 20 = 26 = R(15),
R(16) = R(8) + R(14) = 10 + 26 = 36