Условие:
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. К этой записи дописываются справа ещё два разряда по следующему правилу:
а) складываются все цифры двоичной записи числа N, и остаток от деления суммы на 2 дописывается в конец числа (справа).
Например, запись 11100 преобразуется в запись 111001;
б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы её цифр на 2.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью результирующего числа R. Укажите такое наименьшее число N, для которого результат работы данного алгоритма больше числа 77. В ответе это число запишите в десятичной системе счисления.
Решение:
Рассмотрим пошагово, как решить задачу. 1. Пусть дано натуральное число N. Его двоичная запись обозначим как b. Алгоритм действует так: а) Сначала вычисляем сумму цифр двоичной записи числа N (например, для N = 13 (1101₂) сумма равна 1+1+0+1 = 3). Остаток от деления этой суммы на 2 (то есть s mod 2, где s – сумма цифр) дописывается справа к записи b. Обозначим этот дописанный бит как r1. б) Затем берётся полученная запись (b||r1) и опять вычисляется сумма всех её цифр. Остаток от деления этой суммы на 2 дописывается справа. Пусть этот бит равен r2. Таким образом, итоговая двоичная запись...