Биективная нумерация

Система счисления, в которой каждое неотрицательное целое число может быть представлено ровно одним способом.

Биективная нумерация — это любая числовая система , в которой каждое неотрицательное целое число может быть представлено только одним способом с использованием конечной строки цифр . Название относится к биекции (т. е. взаимно-однозначному соответствию), которая существует в этом случае между набором неотрицательных целых чисел и набором конечных строк с использованием конечного набора символов («цифр»).

Большинство обычных систем счисления, таких как общая десятичная система, не являются биективными, поскольку более одной строки цифр могут представлять одно и то же положительное целое число. В частности, добавление ведущих нулей не меняет представленное значение, поэтому «1», «01» и «001» представляют число один . Несмотря на то, что только первая является обычной, тот факт, что возможны и другие, означает, что десятичная система не является биективной. Однако унарная система счисления , имеющая только одну цифру, является биективной.

Биективная база - k нумерация - это биективная позиционная нотация . Она использует строку цифр из набора {1, 2, ..., k } (где k ≥ 1) для кодирования каждого положительного целого числа; позиция цифры в строке определяет ее значение как кратное степени k . Смаллиан (1961) называет эту нотацию k -адической, но ее не следует путать с p -адическими числами : биективные числа - это система для представления обычных целых чисел конечными строками ненулевых цифр, тогда как p -адические числа - это система математических значений, которые содержат целые числа как подмножество и могут нуждаться в бесконечных последовательностях цифр в любом числовом представлении.

Определение

Биективная система счисления с основанием k использует набор цифр {1, 2, ..., k } ( k ≥ 1) для уникального представления каждого неотрицательного целого числа следующим образом:

• Целое число ноль представлено пустой строкой .
• Целое число, представленное непустой строкой цифр

а _н а _{н −1} ... а ₁ а ₀

является

а _н к ^н + а _{н −1} к ^{н −1} + ... + а ₁ к ¹ + а ₀ к ⁰ .

• Цифровая строка, представляющая целое число m > 0, равна

а _н а _{н −1} ... а ₁ а ₀

где

${\displaystyle {\begin{aligned}a_{0}&=m-q_{0}k,&q_{0}&=f\left({\frac {m}{k}}\right)&\\a_{1}&=q_{0}-q_{1}k,&q_{1}&=f\left({\frac {q_{0}}{k}}\right)&\\a_{2}&=q_{1}-q_{2}k,&q_{2}&=f\left({\frac {q_{1}}{k}}\right)&\\&\,\,\,\vdots &&\,\,\,\vdots \\a_{n}&=q_{n-1}-0k,&q_{n}&=f\left({\frac {q_{n-1}}{k}}\right)=0\end{aligned}}}$

и

${\displaystyle f(x)=\lceil x\rceil -1,}$

${\displaystyle \lceil x\rceil }$наименьшее целое число, не меньшее x ( функция потолка ).

Напротив, стандартную позиционную нотацию можно определить с помощью аналогичного рекурсивного алгоритма, где

${\displaystyle f(x)=\lfloor x\rfloor ,}$

Расширение до целых чисел

Для базы , биективная система счисления базы может быть расширена до отрицательных целых чисел таким же образом, как и стандартная система счисления базы, с использованием бесконечного числа цифр , где , представленных в виде бесконечной влево последовательности цифр . Это происходит потому, что суммирование Эйлера ${\displaystyle k>1}$ ${\displaystyle k}$ ${\displaystyle b}$ ${\displaystyle d_{k-1}}$ ${\displaystyle f(d_{k-1})=k-1}$ ${\displaystyle \ldots d_{k-1}d_{k-1}d_{k-1}={\overline {d_{k-1}}}}$

${\displaystyle g({\overline {d_{k-1}}})=\sum _{i=0}^{\infty }f(d_{k-1})k^{i}=-{\frac {k-1}{k-1}}=-1}$

это означает, что

${\displaystyle g({\overline {d_{k-1}}}d_{k})=f(d_{k})\sum _{i=1}^{\infty }f(d_{k-1})k^{i}=1+\sum _{i=0}^{\infty }f(d_{k-1})k^{i}=0}$

и для каждого положительного числа с биективной нумерацией цифровое представление представлено как . Для основания отрицательные числа представлены как с , в то время как для основания отрицательные числа представлены как . Это похоже на то, как в знаковых цифровых представлениях все целые числа с цифровыми представлениями представлены как , где . Это представление больше не является биективным, так как весь набор бесконечных влево последовательностей цифр используется для представления -адических целых чисел , из которых целые числа являются лишь подмножеством. ${\displaystyle n}$ ${\displaystyle d}$ ${\displaystyle {\overline {d_{k-1}}}d_{k}d}$ ${\displaystyle k>2}$ ${\displaystyle n<-1}$ ${\displaystyle {\overline {d_{k-1}}}d_{i}d}$ ${\displaystyle i<k-1}$ ${\displaystyle k=2}$ ${\displaystyle n<-1}$ ${\displaystyle {\overline {d_{k}}}d}$ ${\displaystyle n}$ ${\displaystyle d}$ ${\displaystyle {\overline {d_{0}}}d}$ ${\displaystyle f(d_{0})=0}$ ${\displaystyle k}$

Свойства биективной базы-кцифры

Для данной базы , ${\displaystyle k\geq 2}$

• количество цифр в биективной системе счисления с основанием k, представляющей неотрицательное целое число n, равно

  ${\displaystyle \lfloor \log _{k}((n+1)(k-1))\rfloor }$, ^[1] в отличие от обычных чисел с основанием k ; если k = 1 (т.е. унарное), то количество цифр равно просто n ; ${\displaystyle \lceil \log _{k}(n+1)\rceil }$
  

• наименьшее неотрицательное целое число, представимое в биективной системе счисления с основанием k длины , равно ${\displaystyle \ell \geq 0}$

  ${\displaystyle \mathrm {min} (\ell )={\frac {k^{\ell }-1}{k-1}}}$;

• наибольшее неотрицательное целое число, представимое в биективной системе счисления с основанием k длины , равно ${\displaystyle \ell \geq 0}$

  ${\displaystyle \mathrm {max} (\ell )={\frac {k^{\ell +1}-k}{k-1}}}$, эквивалентно , или ; ${\displaystyle \mathrm {max} (\ell )=k\times \mathrm {min} (\ell )}$ ${\displaystyle \mathrm {max} (\ell )=\mathrm {min} (\ell +1)-1}$

• биективные числа с основанием k и обычные числа с основанием k для неотрицательного целого числа n идентичны тогда и только тогда, когда обычное число не содержит цифру 0 (или, что эквивалентно, биективное число не является ни пустой строкой, ни содержит цифру k ).

Для данной базы , ${\displaystyle k\geq 1}$

• существует ровно столько биективных чисел с основанием k длины ; ^[2] ${\displaystyle k^{\ell }}$ ${\displaystyle \ell \geq 0}$
• список биективных чисел с основанием k , в естественном порядке представленных целых чисел, автоматически находится в порядке shortlex (кратчайшие первыми, лексикографически в пределах каждой длины). Таким образом, используя λ для обозначения пустой строки , числа с основанием 1, 2, 3, 8, 10, 12 и 16 будут следующими (где обычные представления перечислены для сравнения):

Примеры

34152 (в биективной системе счисления с основанием 5) = 3×5 ⁴ + 4×5 ³ + 1×5 ² + 5×5 ¹ + 2×1 = 2427 (в десятичной системе).

119A (в десятичной системе счисления, где «A» представляет цифровое значение десять) = 1×10 ³ + 1×10 ² + 9×10 ¹ + 10×1 = 1200 (в десятичной системе счисления).

Типичный алфавитный список, содержащий более 26 элементов, является биективным и использует порядок A, B, C...X, Y, Z, AA, AB, AC...ZX, ZY, ZZ, AAA, AAB, AAC...

Биективная система счисления с основанием 10

Биективная система счисления с основанием 10 — это позиционная система счисления с основанием 10 , в которой для представления нуля не используется цифра . Вместо этого в ней есть цифра для представления десяти, например, A.

Как и в обычной десятичной системе , каждая цифра представляет собой степень десяти, так, например, 123 — это «сто плюс два десятка плюс три единицы». Все положительные целые числа , представленные исключительно ненулевыми цифрами в обычной десятичной системе (например, 123), имеют одинаковое представление в биективной десятичной системе счисления. Те, которые используют ноль, должны быть переписаны, так, например, 10 становится A, обычная 20 становится 1A, обычная 100 становится 9A, обычная 101 становится A1, обычная 302 становится 2A2, обычная 1000 становится 99A, обычная 1110 становится AAA, обычная 2010 становится 19AA и так далее.

Сложение и умножение в этой системе по сути такие же, как и в обычной десятичной, за исключением того, что переносы происходят, когда позиция превышает десять, а не когда она превышает девять. Таким образом, для вычисления 643 + 759 есть двенадцать единиц (напишите 2 справа и перенесите 1 в разряд десятков), десять десятков (напишите A без необходимости переноса в разряд сотен), тринадцать сотен (напишите 3 и перенесите 1 в разряд тысяч) и одна тысяча (напишите 1), чтобы получить результат 13A2 вместо обычного 1402.

Биективная система счисления с основанием 26

В биективной системе счисления с основанием 26 можно использовать буквы латинского алфавита от «A» до «Z» для представления 26-значных значений от одного до двадцати шести . (A=1, B=2, C=3, ..., Z=26)

При таком выборе обозначения последовательность чисел (начиная с 1) начинается с A, B, C, ..., X, Y, Z, AA, AB, AC, ..., AX, AY, AZ, BA, BB, BC, ...

Каждая цифровая позиция представляет собой степень числа двадцать шесть, так, например, число WI представляет значение 23 × 26 ¹ + 9 × 26 ⁰ = 607 в десятичной системе счисления.

Многие электронные таблицы , включая Microsoft Excel, используют эту систему для назначения меток столбцам электронной таблицы, начиная с A, B, C, ..., Z, AA, AB, ..., AZ, BA, ..., ZZ, AAA и т. д. Например, в Excel 2013 может быть до 16384 столбцов (2 ¹⁴ в двоичном коде), помеченных от A до XFD. ^{[3] Варианты} вредоносных программ также именуются с использованием этой системы: например, первый распространенный макровирус Microsoft Word, Concept, официально называется WM/Concept.A, его 26-й вариант WM/Concept.Z, 27-й вариант WM/Concept.AA и т. д. Вариант этой системы используется для именования переменных звезд . ^[4] Его можно применять к любой проблеме, где желательно систематическое именование с использованием букв, при этом используя максимально короткие строки.

Исторические заметки

Тот факт, что каждое неотрицательное целое число имеет уникальное представление в биективной системе счисления с основанием k ( k ≥ 1), является « народной теоремой », которая была открыта заново много раз. Ранние примеры — Фостер (1947) для случая k = 10, а также Смаллян (1961) и Бём (1964) для всех k ≥ 1. Смаллян использует эту систему для предоставления гёделевской нумерации строк символов в логической системе; Бём использует эти представления для выполнения вычислений на языке программирования P′′ . Кнут (1969) упоминает особый случай k = 10, а Саломаа (1973) обсуждает случаи k ≥ 2. Форслунд (1995) представляется еще одним переоткрытием и выдвигает гипотезу, что если древние системы счисления использовали биективное основание k , они могли не распознаваться как таковые в археологических документах из-за общей неосведомленности об этой системе.

Примечания

1. "Сколько цифр в биективной системе счисления с основанием k для n?". Stackexchange . Получено 22 сентября 2018 г. .
2. Форслунд (1995).
3. Харви, Грег (2013), Excel 2013 для чайников , John Wiley & Sons, ISBN 9781118550007.
4. Хелльер, Коэль (2001), «Приложение D: Номенклатура переменных звезд», Катаклизмические переменные звезды — как и почему они меняются, Praxis Books in Astronomy and Space, Springer, стр. 197, ISBN 9781852332112.

Ссылки

• Бём, К. (июль 1964 г.), «О семействе машин Тьюринга и связанном с ними языке программирования», ICC Bulletin , 3 : 191.
• Форслунд, Роберт Р. (1995), «Логическая альтернатива существующей позиционной системе счисления», Southwest Journal of Pure and Applied Mathematics , 1 : 27–29, MR  1386376, S2CID  19010664.
• Фостер, Дж. Э. (1947), «Система счисления без символа нуля», Mathematics Magazine , 21 (1): 39–41, doi :10.2307/3029479, JSTOR  3029479.
• Кнут, Д.Э. (1969), Искусство программирования, т. 2: Получисленные алгоритмы (1-е изд.), Эддисон-Уэсли, Решение упражнения 4.1-24, стр. 195. (Обсуждается биективная система счисления с основанием 10.)
• Саломаа, А. (1973), Формальные языки , Academic Press, Примечание 9.1, стр. 90–91. (Обсуждается биективная база k для всех k ≥ 2.)
• Смаллиан, Р. (1961), «9. Лексикографическое упорядочение; n-адическое представление целых чисел», Теория формальных систем , Анналы математических исследований, т. 47, Princeton University Press, стр. 34–36.