Автомат обрабатывает натуральное число N по следующему алгоритму: Строится двоичная запись числа N. Складываются все цифры полученной двоичной записи. В конец записи (справа) дописывается остаток от деления полученной суммы на 2 . Предыдущий пункт

Решение задачи

1. Дано

• Алгоритм обработки натурального числа $N$.
• $N$ — натуральное число ($N \ge 1$).
• Результат работы автомата (число на экране) должен быть меньше 80.

2. Найти

Количество различных чисел, меньших 80, которые могут появиться на экране.

3. Решение

Проанализируем шаги алгоритма.

Пусть $B(N)$ — двоичная запись числа $N$. Пусть $S(B)$ — сумма цифр (битов) в двоичной записи $B$.

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

Шаг 2:

1. Вычисляется сумма цифр $S_1 = S(B(N))$.
2. Дописывается бит четности $p_1 = S_1 \pmod 2$. Новая запи...