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

Решение:

Алгоритм просто удваивает каждый разряд двоичной записи $N$. Если запись $N$ содержит $m$ разрядов, то запись $R$ содержит ровно $2m$ разрядов, причём она составлена из пар 11 и 00.

Чем короче запись $R$, тем меньше само число, поэтому сначала подбираем минимально возможную длину, а затем — минимальное число такой длины.

Числа с $m=2$ (то есть $N=2,3$) дают четырёхразрядное $R\le 1111_2=15\lt 32$ — мало. Значит, нужно $m\ge 3$, и запись $R$ содержит не менее шести разрядов.

Наименьшее шестиразрядное $R$ получается из наименьшего трёхразрядного $N=4=100_2$:

$100_2\to 110000_2=48$.

Действительно, $48\gt 32$, а остальные трёхразрядные $N$ дают больше: $N=5\to 110011_2=51$, $N=6\to 111100_2=60$, $N=7\to 111111_2=63$.

def alg(n):
    return int(''.join(c * 2 for c in bin(n)[2:]), 2)

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

Ответ: 48