Системы счисления

Что проверяет номер

Есть число или выражение в системе с основанием, отличным от 10. Задачи бывают двух видов.

Оба вида решаются перебором. Числа вроде 9**100 Python считает точно и быстро, поэтому хитрых формул не нужно.

База: int, printable и остатки

1. int: читаем запись в системе

int(строка, основание) переводит запись из системы с основанием до 36 в обычное число.

print(int('7ea', 16))
print(int('z', 36))

2. printable: все цифры системы

Строка printable начинается с цифр от 0 до 9, а за ними идут маленькие буквы от a до z. Поэтому printable[:29] это все цифры 29-ричной системы, а printable.index('w') показывает значение цифры w.

from string import printable

print(printable[:29])
print(printable.index('w'))

3. Остатки: достаём цифры числа

x % k это последняя цифра числа в системе с основанием k. x //= k отрезает её. Повторяем, пока число не кончится.

x = 2026
while x != 0:
    print(x % 16)   # цифры идут с конца
    x //= 16

Получили 10, 14, 7 и это те самые 7ea из первого примера, только с конца: a это 10, e это 14.

4. Своя функция перевода

int работает только до основания 36. Если нужно основание больше, пригодится своя функция: каждая цифра умножается на основание в своей степени.

def f(x, o):
    return sum(int(c, 36) * o ** i for i, c in enumerate(reversed(x)))

print(f('7ea', 16))
print(f('z', 36))

reversed(x) идёт с последней цифры, enumerate даёт её номер i, это и есть степень основания.

Считаем цифры в записи

Считаем выражение целиком, потом разбираем его на цифры остатками.

x = 5 * 27 ** 20 + 3 * 9 ** 30 - 2    # выражение из условия
count = 0
while x != 0:
    if x % 27 > 9:                     # цифра больше 9 (в записи была бы буквой)
        count += 1
    x //= 27
print(count)

Для другого вопроса меняется только то, что внутри цикла:

Неизвестная цифра x

Цифры берём из printable, подставляем в запись через f-строку и читаем через int.

from string import printable

for x in printable[:29]:                   # все цифры 29-ричной системы
    x1 = int(f'46{x}19', 29)
    x2 = int(f'3{x}85', 29)
    if (x1 + x2) % 28 == 0:
        print(x, printable.index(x), (x1 + x2) // 28)

Подходят a (значение 10, частное 109490) и o (значение 24, частное 110331). Значения идут по возрастанию, поэтому наименьшему x соответствует первая строка вывода, а наибольшему последняя.

Неизвестное основание и основание больше 36

Неизвестное основание p

Перебираем основание от допустимого минимума до 36. Минимум определяет самая большая цифра в записи: основание должно быть больше неё.

for p in range(13, 37):                    # цифра c это 12, значит p не меньше 13
    x1 = int('2b', p)
    x2 = int('9c', p)
    x3 = int('6', p)
    if (x1 + x2 + x3) % 17 == 0:
        print(p, (x1 + x2 + x3) // 17)

Подходят p = 19 (частное 14) и p = 36 (частное 25). Начать с меньшего основания нельзя: int('9c', 12) падает с ошибкой ValueError, такой цифры в этой системе нет.

Основание больше 36

int читает только до 36, поэтому число собираем руками: цифра умножается на основание в нужной степени.

for x in range(45):                        # цифра x в системе 45: от 0 до 44
    x1 = 7 * 45 ** 2 + x * 45 + 4          # число из цифр 7, x, 4
    x2 = 1 * 45 ** 2 + 40 * 45 + x         # число из цифр 1, 40, x
    if (x1 + x2) % 44 == 0:
        print(x, (x1 + x2) // 44)

Если цифра в условии записана буквой, её значение даёт int('J', 36). Большие и маленькие буквы тут значат одно и то же.

Перебор x: ровно N нулей

В выражении есть неизвестное x, и нужно такое x, при котором в записи ровно N нужных цифр. Соединяем два приёма: снаружи цикл по x, внутри разбор на цифры.

for x in range(1, 3001):
    n = 7 * 13 ** 150 + 13 ** 100 - 4 * 13 ** 30 - x
    count = 0
    while n:                               # пока n не ноль
        if n % 13 == 0:                    # нулевая цифра
            count += 1
        n //= 13
    if count == 53:
        print(x)

Цикл идёт по 3000 числам, а работает быстро. Если подходит несколько x, вывод будет длинным: наименьшее x это первая строка, наибольшее последняя.

Бывает, что N заранее неизвестно: «при котором нулей максимально». Тогда сначала считаем нули для всех x, запоминаем максимум и его x. Знак >= нужен, если просят наибольшее x: при равном количестве нулей ответ обновляется.

best = 0
ans = 0
for x in range(1, 1001):
    n = 3 ** 60 + 3 ** 30 - x
    count = 0
    while n:
        if n % 3 == 0:
            count += 1
        n //= 3
    if count >= best:          # для наименьшего x здесь был бы знак >
        best = count
        ans = x
print(best, ans)