Обо­зна­чим R(n)  — ко­ли­че­ство про­грамм, ко­то­рые пре­об­ра­зу­ют число 1 в число n. Обо­зна­чим t(n) наи­боль­шее не­чет­ное число, крат­ное трем, не пре­вос­хо­дя­щее n.

Обе ко­ман­ды ис­пол­ни­те­ля уве­ли­чи­ва­ют ис­ход­ное число, по­это­му общее ко­ли­че­ство ко­манд в про­грам­ме не может пре­вос­хо­дить 29.

Верны сле­ду­ю­щие со­от­но­ше­ния:

1.  Если n не де­лит­ся на 3, то тогда R (n) = R(T(n)), так как су­ще­ству­ет

един­ствен­ный спо­соб по­лу­че­ния n из T(n) - при­бав­ле­ни­ем двоек.

2.  Пусть n де­лит­ся на 3.

Тогда R (n) = R(n/3)+R(n-2)= R(n/3)+R(n-6) (если n>6).

При n = 3 вы­пол­не­но: R(n) = 2 (два спо­со­ба: при­бав­ле­ни­ем двой­ки или

умно­же­ни­ем на 3).

По­это­му до­ста­точ­но по ин­дук­ции вы­чис­лить зна­че­ния R(n) для всех нечётных

чисел, крат­ных трём и не пре­вос­хо­дя­щих 59.

Имеем:

R(1)= 1

R(3) = 2 = R(5)=R(7)

R(9) = R(9/3) + R(9-6) = R(3) + R(3) =2+2 = 4 = R(11) = R(13)

R(15) = R(5)+R(9) =2+4 =6 = R(17)=R(19)

R(21) = R(7) + R(15) = 2+6 = 8 = R(23)=R(25)

R(27) = R(9) + R(21) =4+8 =12 = R(29) = R(31)

R(33) = R(11)+R(27) = 4+12 = 16 = R(35) = R(37)

R(39) = R(13)+R(33) = 4+16 = 20 = R(41) = R(43)

R(45) = R(15)+R(39) = 6+ 20 = 26 = R(47) = R(51)

R(51) = R(17)+R(45) = 6 + 26 = 32 = R(53) = R(55)

R (57) = R(19)+R(51) = 6 + 32 = 38 = R(59)

Ответ: 38.

Дру­гой спо­соб ре­ше­ния

Ко­ли­че­ство про­грамм, ко­то­рые пре­об­ра­зу­ют число 1 в число n, будем обо­зна­чать через R(n). Оче­вид­но, если n - чётное, то R(n) = 0. По­это­му ниже будем рас­смат­ри­вать толь­ко нечётные числа n.

Будем ре­шать по­став­лен­ную за­да­чу по­сле­до­ва­тель­но для чисел 1, 3, 5,..., 59 (то есть для каж­до­го из чисел опре­де­лим, сколь­ко про­грамм ис­пол­ни­те­ля су­ще­ству­ет для его по­лу­че­ния). Ко­ли­че­ство про­грамм, ко­то­рые пре­об­ра­зу­ют число 1 в число n, будем обо­зна­чать через R(n). Число 1 у нас уже есть, зна­чит, его можно по­лу­чить с по­мо­щью «пу­стой» про­грам­мы. Любая не­пу­стая про­грам­ма уве­ли­чит ис­ход­ное число, т. е. даст число, боль­ше 1. Зна­чит, R(1) = 1. Для каж­до­го сле­ду­ю­ще­го нечётного числа рас­смот­рим, из ка­ко­го числа оно может быть по­лу­че­но за одну ко­ман­ду ис­пол­ни­те­ля. Если число не де­лит­ся на 3, то оно может быть по­лу­че­но толь­ко из преды­ду­ще­го нечётного числа с по­мо­щью ко­ман­ды при­бавь 2. Зна­чит, ко­ли­че­ство ис­ко­мых про­грамм для та­ко­го числа равно ко­ли­че­ству про­грамм для преды­ду­ще­го нечётного числа:

Если число на 3 де­лит­ся, то ва­ри­ан­тов по­след­ней ко­ман­ды два: при­бавь 2 и умножь на 3, тогда За­пол­ним со­от­вет­ству­ю­щую таб­ли­цу по при­ведёным фор­му­лам слева на­пра­во:

При этом ячей­ки, от­но­ся­щи­е­ся к чис­лам, ко­то­рые не де­лят­ся на 3, можно в ре­ше­нии и опу­стить (за ис­клю­че­ни­ем пер­во­го и по­след­не­го чисел):

Ответ: 38.

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