Автомат обрабатывает натуральное число N по следующему алгоритму. 1. Строится двоичная запись числа N. 2. Складываются все цифры полученной двоичной записи. В конец записи…
Автомат обрабатывает натуральное число N по следующему алгоритму. 1. Строится двоичная запись числа N. 2. Складываются все цифры полученной двоичной записи. В конец записи (справа) дописывается остаток от деления суммы на 2. 3. Предыдущий пункт повторяется для записи с добавленной цифрой. 4. Результат переводится в десятичную систему и выводится на экран. Пример. Дано число N = 14. Алгоритм работает следующим образом. 1. Двоичная запись числа N: 1110. 2. Сумма цифр двоичной записи — 3; остаток от деления на 2 равен 1; новая запись 11101. 3. Сумма цифр полученной записи - 4; остаток от деления на 2 равен 0; новая запись 111010. 4. На экран выводится число 57. Укажи наименьшее число, большее 41, которое может появиться на экране в результате работы автомата.
Ответ: \(46\).
Пусть \(k\) — остаток от деления количества единиц в двоичной записи \(N\) на 2.
После первого дописывания получается цифра \(k\). При втором шаге сумма единиц изменяется на \(k\), поэтому новая последняя цифра всегда равна \(0\):
- если \(k=0\), результат равен \(4N\);
- если \(k=1\), результат равен \(4N+2\).
Проверим числа начиная с \(N=10\), так как при \(N\le 9\) результат не превышает \(36\).
- \(N=10\): \(10_{10}=1010_2\), единиц \(2\), поэтому дописываются \(0\) и затем \(0\): \[ 1010\to10100_2=20? \] Важно: после двух дописываний запись имеет вид \(101000_2\), поэтому \[ 101000_2=40. \]
- \(N=11\): \(11_{10}=1011_2\), единиц \(3\): \[ 1011\to10111\to101110_2. \] Переводим: \[ 101110_2=32+8+4+2=46. \]
Число \(40\) ещё не больше \(41\), а следующее возможное число — \(46\). Следовательно, искомый ответ:
\[ \boxed{46} \]
