Ре­ше­ние. Пусть R(n)  — ко­ли­че­ство про­грамм, ко­то­рые число 1 пре­об­ра­зу­ют в число n.

Тогда спра­вед­ли­ва сле­ду­ю­щая фор­му­ла: R(n) = R(n - 1) + R(n - 3).

С её по­мо­щью по­сле­до­ва­тель­но вы­чис­лим зна­че­ния R(n):

R(1) = 1

R(2) = R(1) + R(-1) = 1 + 0 = 1

R(3) = R(2) + R(0) = 1 + 0 = 1

R(4) = R(3) + R(1) = 1 + 1 = 2

R(5) = R(4) + R(2) = 2 + 1 = 3

R(6) = R(5) + R(3) = 3 + 1 = 4

R(7) = R(6) + R(4) = 4 + 2 = 6

R(8) = R(7) + R(5) = 6 + 3 = 9

R(9) = R(8) + R(6) = 9 + 4 = 13

R(10) = R(9) + R(7) = 13 + 6 = 19

Так как в тра­ек­то­рии долж­но при­сут­ство­вать число 10, то для всех сле­ду­ю­щих R(n) нель­зя ис­поль­зо­вать при пе­ре­счёте R(m) такие, что m < 10.

R(11) = R(10) = 19

Число 12 на­о­бо­рот, не долж­но встре­чать­ся в тра­ек­то­рии, по­это­му не будем счи­тать R(12), а все сле­ду­ю­щие R(n) будем пе­ре­счи­ты­вать без R(12).

R(13) = R(10) = 19

R(14) = R(13) + R(11) = 19 + 19 = 38

R(15) = R(14) = 38

Ответ: 38.

При­ведём дру­гое ре­ше­ние на языке Python.