Задание №5 — Анализ простейших алгоритмов

Решение:

Обозначим $M=N-(N\bmod 4)$ — результат первого шага. Это ближайшее снизу число, кратное 4, и при переборе всех $N$ величина $M$ пробегает в точности все кратные четырём числа.

Пусть в двоичной записи $M$ ровно $k$ единиц и $p=k\bmod 2$. На шаге 3а справа приписывается $p$. После этого сумма цифр равна $k+p$ — она чётна при любом $k$, поэтому на шаге 3б приписывается 0.

Итак, к записи $M$ всегда приписываются два разряда $p$ и 0, то есть $R=4M+2p$, где $p$ — чётность количества единиц в $M$.

Условие $R\lt 64$ даёт $4M\le 4M+2p\lt 64$, то есть $M\lt 16$. С учётом кратности четырём получаем $M\le 12$.

Проверим $M=12=1100_2$: единиц две, $p=0$, запись $1100\to 11000\to 110000$, то есть $R=48\lt 64$ — подходит. Следующее значение $M=16=10000_2$ даёт $p=1$ и $R=4\cdot 16+2=66$ — уже не подходит.

Значит, $N-(N\bmod 4)=12$. Этому равенству удовлетворяют $N=12,\ 13,\ 14,\ 15$; наибольшее из них — 15.

def alg(n):
    b = bin(n - n % 4)[2:]
    b += str(sum(map(int, b)) % 2)
    b += str(sum(map(int, b)) % 2)
    return int(b, 2)

print(max(n for n in range(1, 1000) if alg(n) < 64))

Ответ: 15