Question

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

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

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

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

Accepted Answer

126

Answer

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

Алгоритм работает так: берём двоичное представление числа $N$, затем дважды добавляем к нему бит, равный остатку от деления суммы единиц текущей последовательности на 2.

Проверим несколько чисел:

- $N = 15$: двоичная запись $1111_2$, сумма разрядов = 4, остаток = 0, добавляем 0 → $11110_2$, сумма = 4, остаток = 0, добавляем 0 → $111100_2 = 60_{10}$.
- $N = 31$: двоичная запись $11111_2$, сумма разрядов = 5, остаток = 1, добавляем 1 → $111111_2$, сумма = 6, остаток = 0, добавляем 0 → $1111110_2 = 126_{10}$.

Проверим, что 126 действительно получается из некоторого $N$:

$126_{10} = 1111110_2$ — это 7-битное число. Исходное число должно быть 5-битным. Отбросим последние два бита: $11111_2 = 31_{10}$.

Применим алгоритм к 31:
- Двоичная запись: $11111_2$
- Сумма разрядов: 5, остаток от деления на 2: 1, добавляем 1 → $111111_2$
- Сумма разрядов: 6, остаток от деления на 2: 0, добавляем 0 → $1111110_2 = 126_{10}$

Проверим числа меньше 126:

- $124_{10} = 1111100_2$ — исходное число $11111_2 = 31_{10}$, но алгоритм даёт 126, не 124.
- $125_{10} = 1111101_2$ — исходное число $11111_2 = 31_{10}$, но алгоритм даёт 126, не 125.

Используем программный перебор:

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

Программа выводит 126 — это первое число, превышающее 123, которое может быть результатом алгоритма.

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