Question

На вход алгоритма подаётся натуральное число $N$. Алгоритм строит по нему новое число $R$ следующим образом.

1. Строится двоичная запись числа $N$.
2. К этой записи дописываются справа ещё два разряда по следующему правилу:
   - а) складываются все цифры двоичной записи числа $N$, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись $11100_2$ преобразуется в запись $111001_2$;
   - б) над этой записью производятся те же действия — справа дописывается остаток от деления суммы её цифр на 2.

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

**Примеры:** для исходного числа $12_{10} = 1100_2$ результатом является число $110000_2 = 48_{10}$; для исходного числа $7_{10} = 111_2$ это число $11110_2 = 30_{10}$.

Укажите такое **наименьшее** число $N$, для которого результат работы алгоритма больше числа 253. В ответе запишите это число в десятичной системе счисления.

Accepted Answer

64

Answer

Идея решения: перебрать натуральные числа, для каждого применить алгоритм преобразования и найти первое число, при котором результат превышает 253.

Алгоритм работает так:
1. Переводим число $N$ в двоичную запись.
2. Подсчитываем количество единиц в этой записи, берём остаток от деления на 2 и дописываем справа.
3. Повторяем процедуру для полученной строки (подсчитываем единицы в новой строке, берём остаток и дописываем).
4. Переводим результирующую двоичную строку обратно в десятичное число.
5. Проверяем, превышает ли оно 253.

```python
for n in range(1, 100):
    s = bin(n)[2:]
    for i in range(2):
        s += str(s.count('1') % 2)
    r = int(s, 2)
    if r > 253:
        print(n)
        break
```

Проверим вручную для $N = 64$:
- Двоичная запись: $1000000_2$
- Количество единиц: 1, остаток от деления на 2: 1. Дописываем: $10000001_2$
- Количество единиц в $10000001_2$: 2, остаток: 0. Дописываем: $100000010_2$
- Переводим в десятичную: $100000010_2 = 258_{10}$
- $258 > 253$ ✓

Проверим для $N = 63$:
- Двоичная запись: $111111_2$
- Количество единиц: 6, остаток: 0. Дописываем: $1111110_2$
- Количество единиц в $1111110_2$: 6, остаток: 0. Дописываем: $11111100_2$
- Переводим в десятичную: $11111100_2 = 252_{10}$
- $252 
ot> 253$ ✗

Таким образом, наименьшее число $N$, для которого $R > 253$, равно 64.

Задание №5Системы счисления и арифметикаЕГЭ по информатике