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

Решение:

Обозначим $M=N-(N\bmod 8)+(N\bmod 2)$ — результат первого шага. Число $N-(N\bmod 8)$ кратно 8, а прибавляется 0 для чётного $N$ и 1 для нечётного. Значит, $M$ — это число вида $8k$ или $8k+1$, и любое такое число достижимо.

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

Нужно наименьшее $R\gt 97$. Так как $p\le 1$, из $4M+2p\gt 97$ следует $4M\ge 96$, то есть $M\ge 24$. Подходящие значения $M$ — это 24, 25, 32, 33, …

• $M=24=11000_2$: единиц две, $p=0$, $R=96$ — это не больше 97, не подходит;
• $M=25=11001_2$: единиц три, $p=1$, запись $11001\to 110011\to 1100110$, $R=1100110_2=102\gt 97$ — подходит.

Все более крупные $M$ дают $R\ge 4\cdot 32=128$, поэтому наименьшее значение — 102.

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

print(min(r for r in {alg(n) for n in range(1, 1000)} if r > 97))

Ответ: 102