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

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

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)  =  2 (два спо­со­ба: при­бав­ле­ни­ем еди­ни­цы и удво­е­ни­ем). По­это­му до­ста­точ­но по­сте­пен­но вы­чис­лить зна­че­ния R(n) для всех чисел, крат­ных 2 и не пре­вос­хо­дя­щих 20.

Имеем:

R(3)  =  1;

R(4)  =  2  =  R(5);

R(6)  =  R(3) + R(4)  =  1 + 2  =  3  =  R(7);

R(8)  =  R(4) + R(6)  =  2 + 3  =  5  =  R(9);

R(10)  =  R(5) + R(8)  =  2 + 5  =  7  =  R(11);

R(12)  =  R(6) + R(10)  =  3 + 7  =  10  =  R(13);

R(14)  =  R(7) + R(12)  =  3 + 10  =  13  =  R(15);

R(16)  =  R(8) + R(14)  =  5 + 13  =  18  =  R(17);

R(18)  =  R(9) + R(16)  =  5 + 18  =  23  =  R(19);

R(20)  =  R(10) + R(18)  =  7 + 23  =  30  =  R(21);

R(22)  =  R(11) + R(20)  =  7 + 30  =  37.

Ответ: 37.

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