Задание 5 ЕГЭ: двоичная запись: сумма цифр или остаток

Двоичная запись: сумма цифр или остаток. Тема номера — алгоритм построения числа. Ниже — пример с ответом и решением; кнопкой под ним можно решить такую же задачу с другими числами, ответ проверится сразу.

Пример

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.

1. Строится двоичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
  а) если число N делится на 5, то к этой записи дописываются её три последние двоичные цифры;
  б) если число N на 5 не делится, то остаток от деления на 5 умножается на 2, переводится в двоичную запись и дописывается в конец двоичной записи.
Полученная таким образом запись является двоичной записью искомого числа R.
3. Результат переводится в десятичную систему и выводится на экран.

Например, для исходного числа 12₁₀ = 1100₂ результатом является число 1100100₂ = 100₁₀, а для исходного числа 10₁₀ = 1010₂ это число 1010010₂ = 82₁₀.

Укажите минимальное число R, которое может быть результатом работы данного алгоритма, при условии, что N не меньше 13. В ответе запишите это число в десятичной системе счисления.

Решение

Правило проще всего применить программой: строим запись N, обрабатываем её по правилу и переводим результат в десятичную систему. Так как к записи всегда что-то дописывается, R больше N, поэтому перебора N до 999 хватает с запасом.

Для N = 13, 14, … получаем R = 110, 232, 127, 66, 140, 150, 312, 164, 86, 180, … Значения растут неравномерно: разные ветки правила дописывают разное количество разрядов, поэтому нужно проверять все N, а не останавливаться на первом «похожем».

Нужное значение получается при N = 16 = 10000₂: R = 1000010₂ = 66. В ответ идёт R: 66.

def R(n):
    s = bin(n)[2:]
    if n % 5 == 0:
        s = s + s[-3:]                 # последние цифры записи
    else:
        s = s + bin(n % 5 * 2)[2:]     # остаток * 2 в двоичной записи
    return int(s, 2)

print(min(R(n) for n in range(13, 1000)))

Решить такую задачу — новый вариант с проверкой