Задание 5. Информатика. ЕГЭ. Поляков-6535

(А. Богданов) Назовём битом чётности остаток от деления числа единиц двоичной записи на \(2.\) На вход алгоритма подаётся натуральное число \(N.\) Алгоритм строит по нему новое число \(R\) следующим образом:

1. Строится двоичная запись числа \(N.\)
2. Если двоичная запись задаёт нечётное число и её бит чётности равен \(1,\) то к этой записи слева дописывается \(1;\) в противном случае справа дописывается бит чётности.
3. Шаг 2 повторяется.
4. Полученная таким образом запись является двоичной записью искомого числа \(R.\)

Например, для исходного числа \(12 = 1100_2\) результатом является число \(110000_2 = 48,\) а для исходного числа \(4 = 100_2\) результатом является число \(10010_2 = 18.\) Укажите максимальное число \(N,\) после обработки которого с помощью этого алгоритма получается число \(R,\) меньшее \(100.\)

def R(N):
    bn = f'{N:b}'
    for _ in range(2):
        parity_bit = bn.count('1') & 1
        bn = '1' + bn if bn[-1] == '1' and parity_bit else bn + str(parity_bit)
    return int(bn, 2)

print(max(N for N in range(1, 100) if R(N) < 100))