Задание 5

На вход алгоритма подаётся натуральное число N.

Алгоритм строит по нему новое число R следующим образом.

1. Строится двоичная запись числа N.

2. К этой записи дописываются справа ещё два разряда по следующему правилу:

а) складываются все цифры двоичной записи числа N, и остаток от деления суммы на 2 дописывается в конец числа (справа).

Например, запись 11100 преобразуется в запись 111001;

б) над этой записью производятся те же действия — справа дописывается остаток от деления суммы её цифр на 2.

Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.

Например, для исходного числа 12₁₀ = 1100₂ результатом является число 110000₂ = 48₁₀, а для исходного числа 7₁₀ = 111₂ это число 11110₂ = 30₁₀.

Укажите такое наименьшее число N, для которого результат работы алгоритма больше числа 253.

В ответе запишите это число в десятичной системе счисления.

Решение

🔹 Шаг 1. Перебор чисел и двоичная запись

for N in range(1, 20):
    R = f'{N:b}'
    print(N, '→', R)

📌 Результат: 1 → 1, 2 → 10, 3 → 11, 19 → 10011 и т.д.

🔹 Шаг 2. Остаток от деления суммы цифр на 2

for N in range(1, 20):
    R = f'{N:b}'
    bit = R.count('1') % 2
    print(N, R, '→ дописать', bit)

📌 Результат: 1 1 → дописать 1, 2 10 → дописать 1, 3 11 → дописать 0, 19 10011 → дописать 1 и т.д.

🔹 Шаг 3. Дописывание двух разрядов справа

for N in range(1, 20):
    R = f'{N:b}'
    R = R + str(R.count('1') % 2)
    R = R + str(R.count('1') % 2)
    print(N, '→', R)

📌 Результат: 1 → 110, 2 → 1010, 3 → 1100, 19 → 1001110 и т.д.

🔹 Шаг 4. Перевод обратно в десятичное число

for N in range(1, 20):
    R = f'{N:b}'
    R = R + str(R.count('1') % 2)
    R = R + str(R.count('1') % 2)
    print(N, '→', R, '→', int(R, 2))

📌 Результат: 1 → 110 → 6, 2 → 1010 → 10, 3 → 1100 → 12, 19 → 1001110 → 78 и т.д.

🔹 Шаг 5. Поиск первого N, при котором R > 253

Цель: собрать всё вместе и понять задачу целиком.

for N in range(1, 1000):
    R = f'{N:b}'
    R = R + str(R.count('1') % 2)
    R = R + str(R.count('1') % 2)
    R = int(R, 2)
    if R > 253:
        print(N)
        break

📌 Результат: минимальное значение N, при котором R > 253.

Ответ: 64.