Задание 5. На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. К этой записи дописываются справа ещё несколько разрядов по следующему правилу:
а) Если N чётное, то к нему справа приписывается в двоичном виде сумма цифр его двоичной записи;
б) Если N нечётное, то к нему справа приписываются два нуля, а слева единица.
Полученная таким образом запись (в ней как минимум на один разряд больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Например, запись числа 1101 будет преобразована в 11110100. Укажите такое наименьшее число N, для которого результат работы данного алгоритма больше числа 215. В ответе это число запишите в десятичной системе счисления.

Ответ: 23.

Решение:

По условию алгоритм преобразует двоичную запись натурального числа $N$ следующим образом:

• Если число $N$ чётное, справа приписывается двоичная запись суммы единиц в его двоичной записи.

• Если число $N$ нечётное, справа приписываются два нуля, а слева — единица.

Необходимо найти наименьшее натуральное число $N$, для которого полученное число $R>215$.

1. Рассмотрим нечётные числа.

Если двоичная запись числа $N$ содержит 5 разрядов, то после добавления единицы слева и двух нулей справа получаем:

По условию:

Наименьшее нечётное натуральное число, удовлетворяющее этому условию, — 23.

Проверим:

Приписываем справа два нуля:

Приписываем слева единицу:

Переведём результат в десятичную систему счисления:

Получаем:

2. Проверим, нет ли меньшего подходящего числа.

Для $N=21$:

После преобразования:

Все меньшие нечётные числа также дают результат меньше 215.

Для чётных чисел $N\leq22$ сумма единиц двоичной записи не превышает 3. Поэтому справа дописывается не более двух разрядов, а полученное число не превышает:

Следовательно, меньшего подходящего чётного числа тоже нет.

Ответ: $\boxed{23}$.

Примечание: в примере условия, вероятно, допущена опечатка. По указанному правилу число $1101_2$ преобразуется в $1110100_2$, а не в $11110100_2$.