Задание №14. Цифры числа и неизвестные значения

Число задаётся выражением или записью с неизвестной цифрой. Требуется исследовать его запись в указанной системе счисления: посчитать нужные цифры, выполнить условие делимости либо подобрать значение параметра. Большие степени сами по себе не усложняют правило: каждый разряд имеет известный вес, а деление с остатком позволяет последовательно получить все цифры.

Что означает запись числа

Основание системы счисления обозначается b. Нумерация разрядов начинается справа с нуля: их веса равны b^0,b^1,b^2,\ldots. Например, пятеричная запись 234_5 означает 2\cdot5^2+3\cdot5+4=69.

Цифра — знак в записи числа. Её числовое значение может быть больше девяти. При основании 27 разрешены значения от 0 до 26. Значение 10 занимает один разряд, хотя для его десятичного обозначения нужны два символа. Для подсчёта цифр буквенный алфавит вообще не обязателен.

Разбор через веса разрядов

В задании EGE-14-0063 ↗ требуется количество четвёрок в пятеричной записи числа 25^6+5^4-25.

1. Одинаковое основание у степеней

Поскольку 25=5^2, имеем 25^6=5^{12}. Поэтому исходное выражение равно:

5^{12}+(5^4-5^2).

Старший разряд отделён от небольшого фрагмента с вычитанием. Именно в этом фрагменте изменятся цифры.

2. Вычитание с заёмом

Одна единица разряда с весом 5^4 равна пяти единицам разряда с весом 5^3. Одну из них можно разменять ещё на пять единиц следующего разряда. После вычитания 5^2 остаётся:

5^4-5^2=4\cdot5^3+(5-1)\cdot5^2=4\cdot5^3+4\cdot5^2.

Это запись 4400_5. Две четвёрки стоят в разрядах с номерами 3 и 2; младшие разряды нулевые. Десятичная проверка этого фрагмента: 625-25=600=4\cdot125+4\cdot25.

3. Возвращение старшего разряда

Слагаемое 5^{12} добавляет единицу в разряд с номером 12. Слагаемые занимают разные разряды, переноса нет. Полная запись:

1000000004400_5.

В ней одна единица, две четвёрки и десять нулей — всего 13 цифр. Ответ: 2.

Универсальная программа подсчёта

Пусть n — положительное число. При делении на основание b остаток равен младшей цифре: все остальные слагаемые содержат множитель b. Целая часть частного оставляет число без этой цифры. Повторение этих двух действий обходит запись справа налево.

n = 25**6 + 5**4 - 25
count = 0
while n > 0:
    digit = n % 5
    if digit == 4:
        count += 1
    n //= 5
print(count)  # 2

Оператор % получает остаток, // — целое частное. Переменная n уменьшается на каждом шаге, поэтому цикл завершится. Разворачивать полученные цифры не нужно: количество не зависит от порядка. Для восстановления самой записи порядок остатков пришлось бы обратить.

Цикл подходит и для основания 64, как в EGE-14-0040 ↗: там получаются 287 нулей. Все вычисления выполняются с целыми числами. Степень в Python записывается как **; знак ^ означает другую операцию. Для исходного числа 0 нужен отдельный случай: его запись содержит одну цифру, а цикл while n > 0 не выполнится ни разу.

Неизвестная цифра и делимость

В EGE-14-0004 ↗ дана сумма \overline{923x874}_{29}+\overline{524x6152}_{29}. Буква x обозначает одну и ту же цифру в обеих записях, поэтому 0\le x\le28. Нужно выбрать наибольшую цифру, при которой сумма делится на 28, а в ответ записать частное.

Число 29 при делении на 28 даёт остаток 1; любая его неотрицательная целая степень тоже даёт остаток 1. Поэтому для проверки делимости каждое число можно заменить суммой значений его цифр:

(9+2+3+x+8+7+4)+(5+2+4+x+6+1+5+2)=58+2x.

В допустимом диапазоне эта сумма меняется от 58 до 114. Кратные 28 внутри диапазона — 84 и 112. Уравнения 58+2x=84 и 58+2x=112 дают x=13 и x=27. Требуется второе значение.

Сумма цифр помогает проверить делимость, но не заменяет исходное число при вычислении частного. Для получения значения записи удобно последовательно присоединять цифры слева направо: уже прочитанная часть умножается на основание, затем прибавляется следующая цифра.

def value(digits, base):
    result = 0
    for digit in digits:
        result *= base
        result += digit
    return result

x = 27
s = value(
    [9, 2, 3, x, 8, 7, 4], 29
)
s += value(
    [
        5, 2, 4, x,
        6, 1, 5, 2,
    ],
    29,
)
print(s)       # 92937536160
print(s % 28)  # 0
print(s // 28) # 3319197720

Ответ: 3319197720. Если делитель не связан с основанием таким простым образом, эта же функция позволяет проверить все допустимые цифры: вычислить сумму и проверить нулевой остаток от её деления.

Параметр, от которого зависит число нулей

В EGE-14-0012 ↗ исследуется 7^{170}+7^{100}-x, где 1\le x\le2030. Здесь x — целое вычитаемое, а не цифра. Сначала требуется максимальное число нулей в семеричной записи, затем наибольший параметр среди значений, дающих этот максимум.

def zeros(n, base):
    count = 0
    while n > 0:
        if n % base == 0:
            count += 1
        n //= base
    return count

best_count = -1
best_x = None
for x in range(1, 2031):
    count = zeros(
        7**170 + 7**100 - x, 7
    )
    if count >= best_count:
        best_count = count
        best_x = x
# 73 1715
print(best_count, best_x)

Перебор конечен и охватывает весь диапазон, включая 2030. При новом рекорде сохраняется число нулей и соответствующий параметр. При равенстве рекорду параметр тоже заменяется: перебор идёт по возрастанию, значит новое значение больше предыдущего. Ответ: 1715.

Слово «ровно» задаёт другую проверку. В EGE-14-0005 ↗ нужны ровно 202 нуля в записи 9\cdot11^{350}+8\cdot11^{150}-x при 1\le x\le3000. Здесь сохраняются только параметры с count == 202; наибольший равен 2662. Максимизировать само число нулей в этой задаче не требуется.

Возможные ловушки

• Чётность ограничена десятичными цифрами. В EGE-14-0001 ↗ основание равно 36. Чётными могут быть значения 32 и 34; нуль тоже чётный. Проверка только списка 2,4,6,8 теряет подходящие разряды. Проверяется остаток значения цифры при делении на два.
• Добавлены или удалены нули. В EGE-14-0037 ↗ считаются нули самой записи. Внутренние и конечные учитываются, ведущие не приписываются. Иначе ответ начинает зависеть от выбранной ширины записи.
• Значение цифры принято за строку. В EGE-14-0002 ↗ цифра со значением больше девяти считается один раз. Разбиение её десятичного обозначения на символы меняет предмет подсчёта.
• Перепутаны минимум, максимум и ответ. В EGE-14-0017 ↗ нужна наименьшая подходящая цифра, а в разобранном EGE-14-0004 — наибольшая. После выбора в обоих случаях требуется частное; найденная цифра ещё не является ответом.