Арифметика и свойства записи числа

Столбиком в любой системе; остатки, сдвиги, полезные функции

Алгоритм тот же, что в десятичной, только перенос возникает при достижении b (а не 10), и при вычитании занимаем b, а не 10.

сложение// 23₅ + 14₅  (перенос при 5)
  235
+ 145
-----
  42₅
разряд 0: 3 + 4 = 7 = 1·5 + 2 → 2, перенос 1
разряд 1:  2 + 1 + 1 = 4

вычитание// 31₅ − 12₅  (заём = +5)
  315
- 125
-----
  14₅
разряд 0:  1 − 2 нельзя → (1+5) − 2 = 4
разряд 1:  3 − 1 − 1 = 1

Перемножаем по цифрам с переносом при b; частичные произведения сдвигаем и складываем — ровно как в десятичной.

пример// 23₅ × 3₅
  235
+  35
-----
 124₅
3 × 3 = 9 = 1·5 + 4   →  4, перенос 1
3 × 2 = 6, + 1 = 7 = 1·5 + 2   →  2, старший 1

пример// 101₂ × 11₂  — сдвиг + сложение
    101
  ×  11
  -----
    101      // × младший бит
   101·     // × старший бит, сдвиг влево
  -----
   1111₂     // 5 × 3 = 15 ✓

Деление «уголком» тоже работает в любой системе: на каждом шаге делим текущий остаток на делитель, цифра частного — сколько раз он помещается, затем сносим следующую цифру. Все умножения и вычитания — в той же системе.

деление уголком// 372₈ ÷ 5₈ — всё в восьмеричной
 372 │ 5
−36  │─────
 ──  │ 62
  12 │
− 12 │
  ── │
   0

шаги:  37₈ ÷ 5 = 6  (6×5 = 36₈, ост 1),  сносим 2 → 12₈;   12₈ ÷ 5 = 2  (2×5 = 12₈, ост 0)
проверка:  62₈ × 5₈ = 372₈ ✓   (50 × 5 = 250)

Умножение и деление на b — это сдвиг записи, как умножение на 10 в десятичной:

пример// двоичные сдвиги
1011₂ × 10₂  = 10110₂   // ×2 — сдвиг влево, приписали 0
1011₂ ÷ 10₂  = 101₂     // ÷2 — убрали младший бит
11010110₂ mod 100₂ = 10₂  // последние 2 бита = n mod 4 = 2

≡ — это сравнение, а не равенство: сумма цифр даёт тот же остаток по модулю b−1, но не равна ему. Чтобы получить сам остаток, сумму сворачивают ещё раз, до одной цифры (это цифровой корень): 12345 → 1+2+3+4+5 = 15 → 1+5 = 6 = 12345 mod 9.

Отсюда признак делимости на b−1 (по сумме цифр) и быстрая проверка вычислений: заменяем каждое число суммой его цифр (по модулю b−1) — равенство обязано сохраниться.

проверка умножения// 935 × 7 = 6545  —  «выбрасывание девяток» (b−1 = 9)
935  →  9+3+5 = 17  →  1+7 = 8
7    →  7
8 × 7 = 56  →  5+6 = 11  →  2
6545 →  6+5+4+5 = 20  →  2   // совпало → в цифрах ошибки нет

// в hex — «выбрасывание F-ок» (mod 15): F0F₁₆ → F+0+F = 30 ≡ 0

пример// base 10: делимость на 11 (= 10+1)
1234  →  4 − 3 + 2 − 1 = 2  =  1234 mod 11   // не делится

// base 2: остаток по 3 (= 2+1)
1011₂  →  1 − 1 + 0 − 1 = −1 ≡ 2 (mod 3)  =  11 mod 3

Аналогично в восьмеричной знакочередующаяся сумма цифр даёт остаток по 9, в шестнадцатеричной — по 17.

python# базовый набор функций
import string
DIGITS = string.digits + string.ascii_uppercase   # "0123456789ABCDEF…Z" - полезные константы

# 10 → b: запись числа n в системе счисления b (n: str - строка)
def to_base(n, b):  
    if n == 0:
        return "0"
    s = ""
    while n > 0:
        s = DIGITS[n % b] + s    # остаток — очередная цифра
        n //= b
    return s

# b → 10: число из строки, записанной в системе счисления b
def from_base(s, b):
    return int(s, b)             # int("3A7", 16) == 935

# сумма цифр числа n в системе b 
def digit_sum(n, b):
    total = 0
    for c in to_base(n, b):
        total += int(c, b)       # int("A", 16) == 10
    return total

# число разрядов в записи n (n > 0)
def num_digits(n, b):
    return len(to_base(n, b))

# последние k цифр записи — как число
def last_k(n, b, k):
    return n % (b ** k)          # b**k «отрезает» хвост

# сколько нулей в конце записи
def trailing_zeros(n, b):
    z = 0
    while n > 0 and n % b == 0:
        n //= b
        z += 1
    return z

пример// base 6 = 2·3: на КАЖДЫЙ нуль нужны одна 2 и одна 3
12 = 2·2·3      двоек 2, троек 1   →   нулей = min(2,1) = 1   →   12 = 20₆
36 = 2·2·3·3    двоек 2, троек 2   →   нулей = min(2,2) = 2   →   36 = 100₆

// лишняя двойка в 12 простаивает — пары-тройки для второго нуля нет

В задачах эти тождества превращают «найти остаток огромного числа» в арифметику с цифрами — без перевода всего числа.

Сколько раз простое p входит в разложение n! (а значит — какая наибольшая степень p делит n! и сколько нулей у n! по основанию-кратному p):

Та же величина выражается через сумму цифр числа n в системе p (привет разделу 5):

пример// сколько раз 5 входит в 100! (= сколько нулей в конце 100!)
v₅(100!) = ⌊100/5⌋ + ⌊100/25⌋ = 20 + 4 = 24

// та же величина через сумму цифр: 100 = 400₅, S₅ = 4
         = (100 − 4) / (5 − 1) = 96 / 4 = 24

// двоек в 100! больше: v₂ = 50+25+12+6+3+1 = 97
нулей в конце 100! = min(97, 24) = 24   // ограничивает пятёрка

Так решается типовая задача ИТМО: «на какую степень p делится n!» или «сколькими нулями оканчивается n!» — без вычисления самого факториала.