Задание 5 ЕГЭ: запись в других системах счисления

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

Пример

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

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

Например, для исходного числа 14₁₀ = 112₃ результатом является число 11211₃ = 130₁₀, а для исходного числа 9₁₀ = 100₃ это число 10000₃ = 81₁₀.

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

Решение

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

Для N = 1, 2, … получаем R = 5, 22, 30, 14, 49, 60, 23, 76, 81, 32, … Значения растут неравномерно: разные ветки правила дописывают разное количество разрядов, поэтому нужно проверять все N, а не останавливаться на первом «похожем».

Нужное значение получается при N = 42 = 1120₃: R = 112020₃ = 384. В ответ идёт N: 42.

def tern(n):                        # троичная запись числа
    s = ""
    while n > 0:
        s = str(n % 3) + s
        n //= 3
    return s

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

print(min(n for n in range(1, 1000) if R(n) >= 375))

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