Задание 5

(В.Лашин) На вход алгоритма подаётся натуральное число N.

Алгоритм строит по нему новое число R следующим образом.

1. Строится троичная запись числа N.

2. Далее эта запись обрабатывается по следующему правилу:

а) если сумма цифр троичной записи числа кратна 9, то к этой записи справа дописывается 2

б) если сумма цифр троичной записи числа не кратна 9, то к этой записи справа дописывается троичная запись остатка от деления суммы цифр записи на 9;

Полученная таким образом запись является троичной записью искомого числа R.

3. Результат переводится в десятичную систему и выводится на экран.

Например, для исходного числа 9 = 100₃ результатом является число 1001₃ = 28.

А для исходного числа 161 = 12222₃ результатом является число 122222₃ = 485

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

В ответе запишите это число в десятичной системе счисления.

Решение

🔹 Шаг 1. Перебор чисел и троичная запись

def f3(x):
    s = ''
    while x:
        x, ost = divmod(x, 3)
        s += str(ost)
    return s[::-1]


for N in range(1, 20):
    s = f3(N)
    print(N, '→', s)

📌 Результат: 1 → 1, 2 → 2, 3 → 10, 19 → 201 и т.д.

🔹 Шаг 2. Проверка кратности суммы цифр на 9

def f3(x):
    s = ''
    while x:
        x, ost = divmod(x, 3)
        s += str(ost)
    return s[::-1]


for N in range(1, 20):
    s = f3(N)
    digit_sum = sum(int(c) for c in s)
    if digit_sum % 9 == 0:
        print(N, s, f'сумма цифр {digit_sum} кратна 9')
    else:
        print(N, s, f'сумма цифр {digit_sum} не кратна 9')

📌 Результат: 1 1 сумма цифр 1 не кратна 9, 2 2 сумма цифр 2 не кратна 9, 3 10 сумма цифр 1 не кратна 9, 19 201 сумма цифр 3 не кратна 9 и т.д.

🔹 Шаг 3. Изменение троичной строки

def f3(x):
    s = ''
    while x:
        x, ost = divmod(x, 3)
        s += str(ost)
    return s[::-1]


for N in range(1, 20):
    s = f3(N)
    digit_sum = sum(int(c) for c in s)

    if digit_sum % 9 == 0:
        s_new = s + '2'
        print(N, s, '→', s_new, '(дописали 2)')
    else:
        s_new = s + f3(digit_sum % 9)
        print(N, s, '→', s_new, f'(дописали {f3(digit_sum % 9)})')

📌 Результат: 1 1 → 11 (дописали 1), 2 2 → 22 (дописали 2), 3 10 → 101 (дописали 1), 19 201 → 20110 (дописали 10) и т.д.

🔹 Шаг 4. Перевод обратно в десятичное число

def f3(x):
    s = ''
    while x:
        x, ost = divmod(x, 3)
        s += str(ost)
    return s[::-1]


for N in range(1, 20):
    s = f3(N)
    digit_sum = sum(int(c) for c in s)

    if digit_sum % 9 == 0:
        s = s + '2'
    else:
        s = s + f3(digit_sum % 9)

    R = int(s, 3)
    print(N, '→', s, '→', R)

📌 Результат: 1 → 11 → 4, 2 → 22 → 8, 3 → 101 → 10, 19 → 20110 → 174 и т.д.

🔹 Шаг 5. Поиск минимального R при N > 166

Цель: собрать всё вместе и понять задачу целиком.

def f3(x):
    s = ''
    while x:
        x, ost = divmod(x, 3)
        s += str(ost)
    return s[::-1]



best_R = None

for N in range(167, 10000):
    s = f3(N)
    digit_sum = sum(int(c) for c in s)
    if digit_sum % 9 == 0:
        s = s + '2'
    else:
        s = s + f3(digit_sum % 9)
    R = int(s, 3)
    if best_R is None or R < best_R:
        best_R = R

print(best_R)

📌 Результат: минимальное значение R при условии N > 166.

Ответ: 647.