Bijective numeration is anynumeral system in which every non-negativeinteger can be represented in exactly one way using a finitestring of digits. The name refers to thebijection (i.e. one-to-one correspondence) that exists in this case between the set of non-negative integers and the set of finite strings using a finite set of symbols (the "digits").

Most ordinary numeral systems, such as the commondecimal system, are not bijective because more than one string of digits can represent the same positive integer. In particular, addingleading zeroes does not change the value represented, so "1", "01" and "001" all represent the numberone. Even though only the first is usual, the fact that the others are possible means that the decimal system is not bijective. However, theunary numeral system, with only one digit,is bijective.

Abijectivebase-k numeration is a bijectivepositional notation. It uses a string of digits from the set {1, 2, ...,k} (wherek ≥ 1) to encode each positive integer; a digit's position in the string defines its value as a multiple of a power ofk.Smullyan (1961) calls this notationk-adic, but it should not be confused with thep-adic numbers: bijective numerals are a system for representing ordinaryintegers by finite strings of nonzero digits, whereas thep-adic numbers are a system of mathematical values that contain the integers as a subset and may need infinite sequences of digits in any numerical representation.

Thebase-k bijective numeration system uses the digit-set {1, 2, ...,k} (k ≥ 1) to uniquely represent every non-negative integer, as follows:

• The integer zero is represented by theempty string.
• The integer represented by the nonempty digit-string

a_na_n−1 ...a₁a₀

is

a_nkⁿ +a_n−1kⁿ⁻¹ + ... +a₁k¹ +a₀k⁰.

• The digit-string representing the integerm > 0 is

a_na_n−1 ...a₁a₀

where

and

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

${\displaystyle \lceil x\rceil }$ being the least integer not less thanx (theceiling function).

In contrast, standardpositional notation can be defined with a similar recursive algorithm where

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

For base${\displaystyle k>1}$, the bijective base-${\displaystyle k}$ numeration system could be extended to negative integersin the same way as the standard base-${\displaystyle b}$ numeral system by use of an infinite number of the digit${\displaystyle d_{k-1}}$, where${\displaystyle f(d_{k-1})=k-1}$, represented as a left-infinite sequence of digits${\displaystyle \dots d_{k-1}{d}_{k-1}{d}_{k-1}=\overline{d_{k-1}}}$. This is because theEuler summation

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

meaning that

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

and for every positive number${\displaystyle n}$ with bijective numeration digit representation${\displaystyle d}$ is represented by${\displaystyle \overline{d_{k-1}}{d}_{k}d}$. For base${\displaystyle k>2}$, negative numbers are represented by${\displaystyle \overline{d_{k-1}}{d}_{i}d}$ with, while for base${\displaystyle k=2}$, negative numbers are represented by${\displaystyle \overline{d_k}d}$. This is similar to how insigned-digit representations, all integers${\displaystyle n}$ with digit representations${\displaystyle d}$ are represented as${\displaystyle \overline{d_0}d}$ where${\displaystyle f(d_0)=0}$. This representation is no longer bijective, as the entire set of left-infinite sequences of digits is used to represent the${\displaystyle k}$-adic integers, of which the integers are only a subset.

For a given base${\displaystyle k\ge 2}$,

• the number of digits in the bijective base-k numeral representing a nonnegative integern is

  ${\displaystyle \lfloor {\log }_k((n+1)(k-1))\rfloor }$,^[1] in contrast to${\displaystyle \lceil {\log }_k(n+1)\rceil }$ for ordinary base-k numerals;
  ifk = 1 (i.e., unary), then the number of digits is justn;

• the smallest nonnegative integer, representable in a bijective base-k numeral of length${\displaystyle \ell \ge 0}$, is

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

• the largest nonnegative integer, representable in a bijective base-k numeral of length${\displaystyle \ell \ge 0}$, is

  ${\displaystyle \mathrm{m}\mathrm{a}\mathrm{x}(\ell )=\frac{k^{\ell +1}-k}{k-1}}$, equivalent to${\displaystyle \mathrm{m}\mathrm{a}\mathrm{x}(\ell )=k\times \mathrm{m}\mathrm{i}\mathrm{n}(\ell )}$, or${\displaystyle \mathrm{m}\mathrm{a}\mathrm{x}(\ell )=\mathrm{m}\mathrm{i}\mathrm{n}(\ell +1)-1}$;

• the bijective base-k and ordinary base-k numerals for a nonnegative integernare identical if and only if the ordinary numeral does not contain the digit0 (or, equivalently, the bijective numeral is neither the empty string nor contains the digitk).

For a given base${\displaystyle k\ge 1}$,

• there are exactly${\displaystyle k^{\ell }}$ bijective base-k numerals of length${\displaystyle \ell \ge 0}$;^[2]
• a list of bijective base-k numerals, in natural order of the integers represented, is automatically inshortlex order (shortest first, lexicographical within each length). Thus, using λ to denote theempty string, the base 1, 2, 3, 8, 10, 12, and 16 numerals are as follows (where the ordinary representations are listed for comparison):

34152 (in bijective base-5) = 3×5⁴ + 4×5³ + 1×5² + 5×5¹ + 2×1 = 2427 (in decimal).

119A (in bijective base-10, with "A" representing the digit value ten) = 1×10³ + 1×10² + 9×10¹ + 10×1 = 1200 (in decimal).

A typical alphabetic list with more than 26 elements is bijective, using the order of A, B, C...X, Y, Z, AA, AB, AC...ZX, ZY, ZZ, AAA, AAB, AAC...

The bijective base-10 system is a baseten positionalnumeral system that does not use a digit to representzero. It instead has a digit to represent ten, such asA.

As with conventionaldecimal, each digit position represents a power of ten, so for example 123 is "one hundred, plus two tens, plus three units." Allpositive integers that are represented solely with non-zero digits in conventional decimal (such as 123) have the same representation in the bijective base-10 system. Those that use a zero must be rewritten, so for example 10 becomes A, conventional 20 becomes 1A, conventional 100 becomes 9A, conventional 101 becomes A1, conventional 302 becomes 2A2, conventional 1000 becomes 99A, conventional 1110 becomes AAA, conventional 2010 becomes 19AA, and so on.

Addition andmultiplication in this system are essentially the same as with conventional decimal, except that carries occur when a position exceeds ten, rather than when it exceeds nine. So to calculate 643 + 759, there are twelve units (write 2 at the right and carry 1 to the tens), ten tens (write A with no need to carry to the hundreds), thirteen hundreds (write 3 and carry 1 to the thousands), and one thousand (write 1), to give the result 13A2 rather than the conventional 1402.

In the bijective base-26 system one may use the Latin alphabet letters "A" to "Z" to represent the 26 digit valuesone totwenty-six. (A=1, B=2, C=3, ..., Z=26)

With this choice of notation, the number sequence (starting from 1) begins A, B, C, ..., X, Y, Z, AA, AB, AC, ..., AX, AY, AZ, BA, BB, BC, ...

Each digit position represents a power of twenty-six, so for example, the numeral WI represents the value23 × 26¹ + 9 × 26⁰ = 607 in base 10.

Manyspreadsheets includingMicrosoft Excel use this system to assign labels to the columns of a spreadsheet, starting A, B, C, ..., Z, AA, AB, ..., AZ, BA, ..., ZZ, AAA, etc. For instance, in Excel 2013, there can be up to 16384 columns (2¹⁴ in binary code), labeled from A to XFD.^[3]Malware variants are also named using this system: for example, the first widespread Microsoft Word macro virus, Concept, is formally named WM/Concept.A, its 26th variant WM/Concept.Z, the 27th variant WM/Concept.AA, et seq. A variant of this system is used to namevariable stars.^[4] It can be applied to any problem where a systematic naming using letters is desired, while using the shortest possible strings.

The fact that every non-negative integer has a unique representation in bijective base-k (k ≥ 1) is a "folk theorem" that has been rediscovered many times. Early instances areFoster (1947) for the casek = 10, andSmullyan (1961) andBöhm (1964) for allk ≥ 1. Smullyan uses this system to provide aGödel numbering of the strings of symbols in a logical system; Böhm uses these representations to perform computations in the programming languageP′′.Knuth (1969) mentions the special case ofk = 10, andSalomaa (1973) discusses the casesk ≥ 2.Forslund (1995) appears to be another rediscovery, and hypothesizes that if ancient numeration systems used bijective base-k, they might not be recognized as such in archaeological documents, due to general unfamiliarity with this system.

• Böhm, C. (July 1964), "On a family of Turing machines and the related programming language",ICC Bulletin,3: 191.
• Forslund, Robert R. (1995), "A logical alternative to the existing positional number system",Southwest Journal of Pure and Applied Mathematics,1:27–29,MR 1386376,S2CID 19010664.
• Foster, J. E. (1947), "A number system without a zero symbol",Mathematics Magazine,21 (1):39–41,doi:10.2307/3029479,JSTOR 3029479.
• Knuth, D. E. (1969),The Art of Computer Programming, Vol. 2: Seminumerical Algorithms (1st ed.), Addison-Wesley, Solution to Exercise 4.1-24, p. 195. (Discusses bijective base-10.)
• Salomaa, A. (1973),Formal Languages, Academic Press, Note 9.1, pp. 90–91. (Discusses bijective base-k for allk ≥ 2.)
• Smullyan, R. (1961),"9. Lexicographical ordering;n-adic representation of integers",Theory of Formal Systems, Annals of Mathematics Studies, vol. 47, Princeton University Press, pp. 34–36.

• Numeral systems
• Non-standard positional numeral systems

• Articles with short description
• Short description matches Wikidata
• Pages using sidebar with the child parameter
• Use dmy dates from July 2020