Цифры и системы счисления

Мы привыкли, что число и то, как оно написано, — одно и то же. Это не так.

Запись 101 в двоичной системе означает пять, в троичной — десять, в десятичной — сто один. Число во всех трёх случаях разное, а строчка одна. И наоборот: пятёрка записывается как 101, 12 и 5 в разных системах — число одно, записи разные.

Число — это количество. Запись — это способ его назвать. Всё занятие про переход между ними.

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

В позиционной системе с основанием $b$ запись $d_k d_{k-1} \ldots d_1 d_0$ означает

Цифры — это числа от 0 до $b - 1$. Когда основание больше десяти, цифр не хватает, и берут буквы: A — это 10, B — 11, и так до Z — 35. Поэтому основание в задачах обычно не превосходит 36.

Заметьте: это ровно то, что мы делали на занятии про разбор числа по цифрам, только там $b$ было всегда равно десяти. Сейчас оно станет параметром.

Из записи в число

Идём по записи слева направо и на каждом шаге умножаем накопленное на основание, прибавляя очередную цифру:

value = 0
for symbol in text:
    value = value * b + DIGITS.index(symbol)

Это короче, чем считать степени: степени тут возникают сами собой. В Python есть и готовое: int("1A", 16) вернёт 26.

Из числа в запись

Обратный ход — деление с остатком. Остаток от деления на $b$ — это последняя цифра, а частное — «всё остальное число»:

out = []
while value > 0:
    out.append(DIGITS[value % b])
    value //= b
text = "".join(reversed(out))

Две ловушки, обе в этих шести строчках.

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

Вторая: при value == 0 цикл не сделает ни одного шага, и результатом будет пустая строка вместо "0". Ноль приходится обрабатывать отдельно — и это единственный случай, когда запись не строится общим правилом.

Из системы в систему

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

Программа переводит число в систему $b$ делением с остатком, но не обрабатывает ноль отдельно.

Что она выведет для $n = 0$?

Сумма цифр считается тем же разбором на разряды. Но у неё есть свойство, которое превращает её из упражнения в инструмент.

Сумма цифр числа в системе $b$ даёт тот же остаток при делении на $b - 1$, что и само число.

Почему? Потому что $b \equiv 1 \pmod{b-1}$, а значит и любая степень $b^k \equiv 1$. Тогда

Каждый разряд «теряет» свою степень основания, и остаётся просто цифра.

Что из этого следует

В десятичной системе $b - 1 = 9$. Отсюда сразу два школьных признака:

• число делится на 9 тогда и только тогда, когда на 9 делится сумма его цифр;
• число делится на 3 тогда и только тогда, когда на 3 делится сумма цифр (потому что 3 делит 9).

Никакой магии, просто $10 \equiv 1 \pmod 9$. В двоичной системе $b - 1 = 1$, и свойство вырождается: по модулю единицы всё равно нулю.

Цифровой корень

Если складывать цифры повторно, пока не останется одна, получится цифровой корень. Из свойства выше он считается формулой без всякого цикла:

root = 0 if n == 0 else 1 + (n - 1) % (b - 1)

Проверьте на примере: для $n = 9999$ в десятичной сумма цифр 36, потом 9. Формула: $1 + 9998 \bmod 9 = 1 + 8 = 9$. Сходится.

Сколько единиц в двоичной записи числа 100? Введите целое число.

Палиндром — запись, которая читается одинаково в обе стороны. Важно, что это свойство записи, а не числа: пятёрка в двоичной системе 101 — палиндром, а в троичной 12 — нет.

Проверка простая: получить список цифр и сравнить его с перевёрнутым.

digits = digits_in_base(n, b)
if digits == digits[::-1]:
    ...

Когда палиндромов надо посчитать много

Перебирать все числа до $n$ годится, пока $n$ не больше миллиона. Для $n$ до $10^{18}$ нужен другой ход.

Палиндром однозначно задаётся своей первой половиной. Возьмём половину 123, отразим — получим 12321 для нечётной длины или 123321 для чётной. Значит палиндромов длины $L$ ровно столько, сколько бывает первых половин: $9 \cdot 10^{\lceil L/2 \rceil - 1}$.

Отсюда и подсчёт, и построение палиндрома по номеру: числа с меньшим количеством цифр считаются формулой, а на последней длине достаточно сравнить построенный палиндром с самим $n$.

Ноль превращается в пустую строку. Разобрано выше. Проверяйте каждое решение на $n = 0$.

Забытый разворот. Цифры выходят с конца. Ошибка коварна тем, что на палиндромах ответ совпадает.

Цифры больше девяти напечатаны как числа. При $b = 16$ десятка должна стать буквой A. Если печатать str(10), получится 10 — две цифры вместо одной, и запись станет неоднозначной.

Обычное деление вместо целочисленного. value / b даёт вещественное число, и на больших значениях цифры «поплывут». Только //.

Ведущие нули. Появляются, если переворачивать запись. Как правило, их надо просто отбросить — но проверьте, что именно требует условие.

Регистр букв. Договоритесь с условием: заглавные или строчные. int(s, b) в Python принимает оба, а вот вывод надо приводить к тому, что просят.

Как проверять себя

• $n = 0$ и $n = 1$;
• $b = 2$ и $b = 36$ — крайние основания;
• $n = b$ — первое число, у которого появляется второй разряд;
• $n = b - 1$ — последнее однозначное.

Лестница прежняя: пять разминочных, семь основных, три со звёздочкой. Зачёт при десяти решённых.

Напишите себе две функции — «запись в число» и «число в запись» — и дальше пользуйтесь ими. Почти половина задач занятия решается их комбинацией.

И проверяйте на нуле. В этом занятии он ломает больше решений, чем все остальные случаи вместе.

Задача: «даны $n$ от 0 до $10^{18}$ и $b$ от 2 до 36; выведите запись числа $n$ в системе с основанием $b$, обозначая цифры больше девяти заглавными латинскими буквами».

Ученик написал:

n, b = map(int, input().split())

digits = ""
while n > 0:
    digits += str(n % b)
    n //= b

print(digits[::-1])

На входах 10 2, 255 8 и 1000 3 ответ верный.

Здесь две независимые ошибки. Найдите обе, приведите к каждой конкретный вход и предложите исправление.