Неизвестное основание и признаки делимости

Дополнительный урок — для продвинутых: на экзаменах такие задачи не встречались, основные подтемы решаются без него.

Неизвестное основание находят той же позиционной формулой, а слишком длинный перебор заменяют рассуждением о записи. Всё нужное уже есть: разложение по степеням и функция value из подтемы 5, функция digits из подтемы 3, блоки записи из подтемы 2. Начнём с вопроса: в какой системе запись 132 означает число 56?

Неизвестное основание определяется через ту же позиционную формулу. Пусть 132 в системе с основанием q равно 56₁₀. Цифра 3 требует q ≥ 4. Раскрываем запись: q² + 3q + 2 = 56. Можно решить уравнение, а можно проверить небольшой диапазон оснований.

Откуда взять верхнюю границу? Первое слагаемое равно q², остальные неотрицательны. Поэтому q² ≤ 56. При q = 8 уже q² = 64 > 56. Значит, 4 ≤ q ≤ 7:

for q in range(4, 8):    print(q, value([1, 3, 2], q))

Получили q = 6. Диапазон перебора основания нужно обосновывать. Граница вроде 1000 сама по себе не доказывает, что большие основания невозможны.

Неизвестное основание и неизвестная цифра ищутся вместе — вложенным перебором с теми же границами. Пусть запись 2x1 в системе с основанием q равна 91. Раскрываем: 2q² + xq + 1 = 91. Ограничения: q ≥ 3 из-за цифры 2, а также 0 ≤ x < q. Кроме того, 2q² ≤ 91; при q = 7 уже 2q² = 98 > 91. Значит, достаточно оснований от 3 до 6:

for q in range(3, 7):    for x in range(q):        if value([2, x, 1], q) == 91:            print(q, x)

Проверка: 231₆ = 2 · 36 + 3 · 6 + 1 = 91.

Равенство с несколькими буквами-цифрами решают перебором основания и всех букв, а первая цифра каждого числа — не ноль. В подборках встречаются равенства вроде 2x + xy = 1y5, где все числа записаны в одной неизвестной системе с основанием q, а x и y — её цифры. Цифра 5 требует q ≥ 6; буква x стоит первой в числе xy, поэтому x ≠ 0.

for q in range(6, 37):    for x in range(1, q):        for y in range(q):            left = value([2, x], q) + value([x, y], q)            if left == value([1, y, 5], q):                print(q, x, y)

Единственное решение: q = 7, x = 5, y = 0. Проверка: 25₇ + 50₇ = 19 + 35 = 54 = 105₇. Требование «первая цифра не ноль» здесь существенно: в задачах подборки без него решений находятся десятки, а с ним — одно.

Граница 36 в программе взята с запасом, и её нужно обосновать. Здесь помогает сложение столбиком из подтемы 2.

Число делится на q − 1 тогда и только тогда, когда на q − 1 делится сумма его цифр. Это полезный дополнительный способ ручного решения; обычный признак делимости на 9 — частный случай для основания 10.

Возьмём сумму 2Ax5₁₆ + 1xB3₁₆, которая должна делиться на 15. Делитель 15 = 16 − 1, поэтому достаточно сложить значения всех цифр обоих слагаемых: 2 + 10 + x + 5 + 1 + x + 11 + 3 = 32 + 2x. Так как 0 ≤ x ≤ 15, то 32 ≤ 32 + 2x ≤ 62, а кратные 15 в этом диапазоне — 45 и 60.

Уравнение 32 + 2x = 45 даёт x = 6,5, что не является цифрой. А 32 + 2x = 60 даёт x = 14 — без перебора.

Для делителя q + 1 вместо обычной суммы берут сумму с чередующимися знаками, начиная с плюса у крайней правой цифры. Например, 314₅ = 3 · 25 + 1 · 5 + 4. Проверка делимости на 6 = 5 + 1: 4 − 1 + 3 = 6. Поэтому число делится на 6. Действительно, 314₅ = 84 = 6 · 14.

Причина чередования: при делении на q + 1 основание q ведёт себя как −1, его квадрат — как 1, куб — снова как −1. Поэтому знакочередующаяся сумма имеет тот же остаток от деления на q + 1, что и само число, — так находят и остаток, а не только делимость.

Для программного решения эти признаки необязательны: обычное вычисление значения и % работает универсально.

Наименьшую положительную добавку до кратного вычисляют без перебора самой добавки: A = N − (M mod N). Пусть нужно найти наименьшее положительное целое A, при котором M + A делится на N, где N > 0. Рассмотрим остаток r = M mod N. Если M = Nk + r, то M + (N − r) = N(k + 1). Следовательно, до следующего кратного не хватает N − r.

Например, M = 100, N = 12: остаток 100 mod 12 = 4, нужно добавить 12 − 4 = 8. Действительно, 100 + 8 = 108 = 12 · 9.

Если M уже делится на N, остаток равен нулю. Тогда минимальная неотрицательная добавка равна 0, а минимальная положительная — N. Формула A = N − (M mod N) даёт именно положительную добавку. Если в условии используется слово «натуральное», внимательно соотнеси его с требованием положительности.

Пример с неизвестной цифрой: M = 2x0₅, N = 1x0₅, нужна минимальная положительная добавка среди всех допустимых x. Здесь M = 50 + 5x, N = 25 + 5x, 0 ≤ x ≤ 4:

answers = [] for x in range(5):    m = value([2, x, 0], 5)    n = value([1, x, 0], 5)     a = n - m % n    answers.append(a) print(answers, min(answers))

Мы перебрали только пять цифр, а каждую добавку вычислили сразу. Наименьшая добавка — 5, при x = 1.

Если ответ про параметр x лежит далеко, начало перебора находят по блокам записи. В двух задачах подборки из суммы степеней вычитают натуральное x без верхней границы, а ответ — около тридцати миллионов. Перебор с единицы идёт около минуты. Разберём такую задачу на своих числах: N = 3 · 6²² + 5 · 6¹² + 4 · 6⁸ + 2 · 6⁵ + 11 − x; нужно наименьшее x, при котором в шестеричной записи N пятёрок больше, чем нулей.

Без x запись состоит из блоков: 3 в разряде 22, 5 в разряде 12, а младший блок L = 4 · 6⁸ + 2 · 6⁵ + 11 = 6734027 занимает разряды 8…0. Между ними нули: девять в разрядах 21…13 и три в разрядах 11…9.

1. Пока x ≤ L, вычитание затрагивает только младший блок: N = 3 · 6²² + 5 · 6¹² + (L − x). Двенадцать нулей в разрядах 21…13 и 11…9 остаются, а пятёрок не больше 1 + 9 = 10. Условие выполниться не может.
2. При x = L + 1 получаем N = 3 · 6²² + 5 · 6¹² − 1 = 3 · 6²² + 4 · 6¹² + (6¹² − 1): двенадцать пятёрок в разрядах 11…0, а нулей девять. Условие выполнено.

Значит, ответ — L + 1, и программа проверяет его сразу, без миллионов шагов:

c = 3*6**22 + 5*6**12 + 4*6**8 + 2*6**5 + 11x = 4*6**8 + 2*6**5 + 11 + 1ds = digits(c - x, 6)print(x, ds.count(5), ds.count(0))

Перебор с единицы прошёл бы 6,7 миллиона значений x; рассуждение о блоках сразу говорит, с какого x начинать.

• Основаниеперебор: снизу — наибольшая цифра, сверху — оценка
• Буквы-цифрыпервая цифра числа — не ноль
• Делимость на q − 1по сумме цифр
• Делимость на q + 1по знакочередующейся сумме
• ДобавкаN − (M mod N)
• Ответ далеконачало перебора — по блокам