Введение

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

Биективная нумерация – это любая числовая система, в которой каждое неотрицательное целое число может быть представлено ровно одним способом с использованием конечной строки цифр. Название происходит от биекции (то есть взаимно однозначного соответствия), существующей в этом случае между множеством неотрицательных целых чисел и множеством конечных строк, составленных из конечного набора символов («цифр»). Большинство обычных систем счисления, таких как десятичная система, не являются биективными, поскольку одно и то же положительное целое число может быть представлено несколькими строками цифр. В частности, добавление ведущих нулей не изменяет значение, поэтому "1", "01" и "001" все представляют число один. Хотя обычно используется только первая запись, возможность других означает, что десятичная система не является биективной. Однако униарная система счисления, использующая только одну цифру, является биективной. Биективная нумерация с основанием k представляет собой биективную позиционную систему счисления. Она использует строку цифр из множества {1, 2, ..., k} (где k ≥ 1) для кодирования каждого положительного целого числа; позиция цифры в строке определяет её значение как кратное некоторой степени k. Эта нотация называется k-адичной, но её не следует путать с p-адическими числами: биективные цифры – это система для представления обычных целых чисел конечными строками ненулевых цифр, в то время как p-адические числа – это система математических значений, содержащая целые числа как подмножество и для представления которых могут потребоваться бесконечные последовательности цифр в любом числовом представлении.

Примеры

34152 (в биективной системе счисления по основанию 5) = 3×5⁴ + 4×5³ + 1×5² + 5×5¹ + 2×1 = 2427 (в десятичной системе счисления). 119A (в биективной системе счисления по основанию 10, где "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 — это позиционная десятичная система счисления, которая не использует цифру для обозначения нуля. Вместо этого в ней используется цифра для обозначения десяти, например, А. Как и в обычной десятичной системе, каждая позиция цифры представляет собой степень десятки, поэтому, например, 123 — это «одна сотня, плюс две десятки, плюс три единицы». Все положительные целые числа, представленные исключительно ненулевыми цифрами в обычной десятичной системе (например, 123), имеют то же представление в биективной системе с основанием 10. Числа, использующие ноль, необходимо переписать: например, 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 числовых значений от 1 до 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. Варианты вредоносных программ также называются с использованием этой системы: например, первый широко распространенный макровирус Microsoft Word, Concept, официально называется WM/Concept.A, его 26-й вариант – WM/Concept.Z, 27-й вариант – WM/Concept.AA и так далее. Вариант этой системы используется для наименования переменных звезд. Её можно применить к любой задаче, где требуется систематическое именование с использованием букв, при этом используя максимально короткие строки.

Исторические примечания

Тот факт, что каждое неотрицательное целое число имеет единственное представление в биективной системе счисления по основанию k (k ≥ 1), является "народной теоремой", которая многократно переоткрывалась. Ранние примеры относятся к случаю k = 10, и для всех k ≥ 1. Смуллиан использует эту систему для построения нумерации Гёделя строк символов в логической системе; Бём использует эти представления для выполнения вычислений в языке программирования P′′. упоминает частный случай k = 10, а обсуждает случаи k ≥ 2. представляется еще одним переоткрытием и выдвигает гипотезу о том, что если древние системы счисления использовали биективную базу k, они могли бы не быть распознаны как таковые в археологических документах из-за общей незнакомости с этой системой.