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

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

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

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

Определение

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

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

а а п п -1 ... а 1 а 0

является

ан к ​ н + а н -1 к п -1 + ... + а 1 к 1 + а 0 к 0

.

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

а а п п -1 ... а 1 а 0

где

{\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}}

и

f(x)=\lceil x\rceil -1,

\lceil x\rceil

являющееся наименьшим целым числом не меньше x ( функция потолка ).

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

f(x)=\lfloor x\rfloor ,

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

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

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

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

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

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

Свойства биективных по основанию k чисел

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

количество цифр в биективном числе по основанию k , представляющем неотрицательное целое число n, равно
$\lfloor \log _{k}((n+1)(k-1))\rfloor$ , ^[1] в отличие от $\lceil \log _{k}(n+1)\rceil$ для обычных с основанием k ; цифр
если k = 1 (т. е. унарный), то количество цифр равно n ;
наименьшее неотрицательное целое число, представимое в виде биективного числа по основанию k длины $\ell \geq 0$ , является
$\mathrm {min} (\ell )={\frac {k^{\ell }-1}{k-1}}$ ;
наибольшее неотрицательное целое число, представимое в виде биективного числа по основанию k длины $\ell \geq 0$ , является
$\mathrm {max} (\ell )={\frac {k^{\ell +1}-k}{k-1}}$ , эквивалентный $\mathrm {max} (\ell )=k\times \mathrm {min} (\ell )$ , или $\mathrm {max} (\ell )=\mathrm {min} (\ell +1)-1$ ;
биективные числа по основанию k и обычные числа по основанию k для неотрицательного целого числа n идентичны тогда и только тогда, когда обычное число не содержит цифру 0 (или, что то же самое, биективное число не является ни пустой строкой, ни содержит цифру k ) .

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

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

биективная база 1:	`λ`	`1`	`11`	`111`	`1111`	`11111`	`111111`	`1111111`	`11111111`	`111111111`	`1111111111`	`11111111111`	`111111111111`	`1111111111111`	`11111111111111`	`111111111111111`	`1111111111111111`	`...`	( унарная система счисления )
биективная база 2:	`λ`	`1`	`2`	`11`	`12`	`21`	`22`	`111`	`112`	`121`	`122`	`211`	`212`	`221`	`222`	`1111`	`1112`	`...`
двоичный:	`0`	`1`	`10`	`11`	`100`	`101`	`110`	`111`	`1000`	`1001`	`1010`	`1011`	`1100`	`1101`	`1110`	`1111`	`10000`	`...`
биективная база 3:	`λ`	`1`	`2`	`3`	`11`	`12`	`13`	`21`	`22`	`23`	`31`	`32`	`33`	`111`	`112`	`113`	`121`	`...`
тройной:	`0`	`1`	`2`	`10`	`11`	`12`	`20`	`21`	`22`	`100`	`101`	`102`	`110`	`111`	`112`	`120`	`121`	`...`
биективная база 8:	`λ`	`1`	`2`	`3`	`4`	`5`	`6`	`7`	`8`	`11`	`12`	`13`	`14`	`15`	`16`	`17`	`18`	`...`
восьмеричный:	`0`	`1`	`2`	`3`	`4`	`5`	`6`	`7`	`10`	`11`	`12`	`13`	`14`	`15`	`16`	`17`	`20`	`...`
биективное основание 10:	`λ`	`1`	`2`	`3`	`4`	`5`	`6`	`7`	`8`	`9`	`A`	`11`	`12`	`13`	`14`	`15`	`16`	`...`
десятичный:	`0`	`1`	`2`	`3`	`4`	`5`	`6`	`7`	`8`	`9`	`10`	`11`	`12`	`13`	`14`	`15`	`16`	`...`
биективное основание 12:	`λ`	`1`	`2`	`3`	`4`	`5`	`6`	`7`	`8`	`9`	`A`	`B`	`C`	`11`	`12`	`13`	`14`	`...`
двенадцатеричный:	`0`	`1`	`2`	`3`	`4`	`5`	`6`	`7`	`8`	`9`	`A`	`B`	`10`	`11`	`12`	`13`	`14`	`...`
биективное основание 16:	`λ`	`1`	`2`	`3`	`4`	`5`	`6`	`7`	`8`	`9`	`A`	`B`	`C`	`D`	`E`	`F`	`G`	`...`
шестнадцатеричный:	`0`	`1`	`2`	`3`	`4`	`5`	`6`	`7`	`8`	`9`	`A`	`B`	`C`	`D`	`E`	`F`	`10`	`...`

Примеры

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

119A (в биективной системе счисления по основанию 10, где «А» представляет цифровое значение десять) = 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

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

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

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

Биективная система по основанию 26.

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

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

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

Многие электронные таблицы , включая 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 , они могли бы не быть признаны таковыми в археологических документах из-за общего незнания этой системы.

Примечания

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

Ссылки

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

[1] «Сколько цифр в биективном числе по основанию k для n?» . Обмен стеками . Проверено 22 сентября 2018 г.

[FOOTNOTEForslund1995-2] Форслунд (1995) .

[3] Харви, Грег (2013), Excel 2013 для чайников , John Wiley & Sons, ISBN 9781118550007 .

[4] Хеллиер, Коэл (2001), «Приложение D: Номенклатура переменных звезд», Катаклизмические переменные звезды - как и почему они изменяются , Книги Praxis Books in Astronomy and Space, Springer, стр. 197, ISBN 9781852332112 .

[1]

[2]

[3]

[4]