Bijective numeration

Bijective numeration
Numeral systems by culture
Hindu-Arabic numerals
Western Arabic (Hindu numerals)
Eastern Arabic
Indian family
Tamil
Burmese
Khmer
Lao
Mongolian
Thai
East Asian numerals
Chinese
Japanese
Suzhou
Korean
Vietnamese
Counting rods
Alphabetic numerals
Abjad
Armenian
Āryabhaṭa
Cyrillic
Ge'ez
Greek (Ionian)
Hebrew
Other systems
Aegean
Attic
Babylonian
Brahmi
Egyptian
Etruscan
Inuit
Kharosthi
Mayan
Quipu
Roman
Sumerian
Urnfield
List of numeral system topics
Positional systems by base
Decimal (10)
2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 20, 24, 30, 36, 60, 64
List of numeral systems
v · d · e

Bijective numeration is any numeral system that establishes a bijection between the set of non-negative integers and the set of finite strings over a finite set of digits. In particular, bijective base-k numeration represents a non-negative integer by using a string of digits from the set {1, 2, ..., k} (k ≥ 1) to encode the integer's expansion in powers of k. (Although slightly misleading, this is the terminology in the literature. Ordinary base-k numeration also establishes a bijection, but not in the required sense, due to the absence of leading zeros; for example, there are only 90 two-digit decimal numerals, rather than the required 102.) Bijective base-k numeration is also called k-adic notation, not to be confused with the p-adic number system. Bijective base-1 is also called unary.

Contents

Definition

The k-adic 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 the empty string.
  • The integer represented by the nonempty digit-string
anan−1 ... a1a0
is
an kn + an−1 kn−1 + ... + a1 k1 + a0 k0.
  • The digit-string representing the integer m > 0 is
anan−1 ... a1a0
where

\begin{align}
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} - 0 k , & & q_n & = & f\left(\frac {q_{n-1}} k \right) & = 0
\end{align}
and
f(x) = \lceil x \rceil - 1,
\lceil x \rceil being the least integer not less than x (the ceiling function).

Properties of bijective base-k numerals

For a given k ≥ 1,

  • there are exactly kn k-adic numerals of length n ≥ 0;
  • if k > 1, the number of digits in the k-adic numeral representing a nonnegative integer n is \lfloor {\color{Blue}\log}_k (n+1) \rfloor, in contrast to {\color{Blue}\lfloor} \log_k {n} +1 {\color{Blue}\rfloor}\ (n > 0) for ordinary base-k numerals; if k = 1 (i.e., unary), then the number of digits is just n;
  • a list of k-adic numerals, in natural order of the integers represented, is automatically in shortlex order (shortest first, lexicographical within each length). Thus, using ε to denote the empty string, the 1-, 2-, 3-, and 10-adic numerals are as follows (where the ordinary binary and decimal representations are listed for comparison):
1-adic: ε 1 11 111 1111 11111 ... (unary numeral system)
2-adic: ε 1 2 11 12 21 22 111 112 121 122 211 212 221 222 1111 1112 ...
binary: 0 1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1110 1111 10000 ...
3-adic: ε 1 2 3 11 12 13 21 22 23 31 32 33 111 112 113 121 ...
10-adic: ε 1 2 3 4 5 6 7 8 9 A 11 12 13 14 15 16 ...
decimal: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ...

Examples

(34152)five-adic = 3×54 + 4×53 + 1×52 + 5×51 + 2×50 = (2427)decimal.
(119A)ten-adic = 1×103 + 1×102 + 9×101 + 10×100 = (1200)decimal.

In the last example, the digit "A" represents the integer ten. For 10 ≤ k ≤ 35, it is common to use successive letters of a common alphabet for the digits after 9; e.g., bijective hexadecimal would use the sixteen digits {1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F, G}.

The bijective base-10 system

The bijective base-10 system is also known as decimal without a zero. It is a base ten positional numeral system that does not use a digit to represent zero. It instead has a digit to represent ten, such as A.

As with conventional decimal, each digit position represents a power of ten, so for example 123 is "one hundred, plus two tens, plus three units." All positive integers which are represented solely with non-zero digits in conventional decimal (such as 123) have the same representation in decimal without a zero. 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 and multiplication in decimal without a zero 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.

The bijective base-26 system

The bijective base-26 system is also known as base 26 without a zero. It is a base twenty-six positional numeral system that does not use a digit to represent zero. It uses digits "A" to "Z" to represent one to twenty-six.

The number sequence goes A, B, C, ..., X, Y, Z, AA, AB, AC, ..., AX, AY, AZ, BA, BB, BC, ... This is what Microsoft Excel uses to identify columns in spreadsheets.

Each digit position represents a power of twenty-six, so for example ABC is "one 262, plus two 261, plus three units (260)" since "A" is worth one, "B" is worth two, "C" is worth three.

In this representation the number WIKIPEDIA is:

23 \times 26^8 + 9 \times 26^7 + 11 \times 26^6 + 9 \times 26^5 + 16 \times 26^4 + 5 \times 26^3 + 4 \times 26^2 + 9 \times 26^1 + 1 \times 26^0 = 4,878,821,185,187

Systematic naming using the alphabet

Many spreadsheets including Microsoft Excel use the 26-adic counting system with the "digits" A-Z to label the columns of a spreadsheet, starting A, B, C... Z, AA, AB... AZ, BA... ZZ, AAA, etc. The numbering starts at 1 or A, so the empty string is not used. A variant of this system is used to name variable stars, it can be applied to any problem where a systematic naming using letters is desired, while using the shortest possible strings.

Historical notes

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 are Smullyan (1961) for the case k = 2, and Böhm (1964) for all k ≥ 1 (the latter using these representations to perform computations in the programming language P′′). Knuth (1969) mentions the special case of k = 10, and Salomaa (1973) discusses the cases k ≥ 2. Forslund (1995) considers that if ancient numeration systems used bijective base-k, they might not be recognised as such in archaeological documents, due to general unfamiliarity with this system. (The latter article is notable in that it does not cite existing literature on this system, but appears to unwittingly reinvent it.)

References

  • Böhm, C. "On a family of Turing machines and the related programming language", ICC Bulletin 3, p. 191, July 1964.
  • Knuth, D. E. The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 1st ed., Addison-Wesley, 1969. (Solution to Exercise 4.1-24, p. 495., discusses bijective base-10.)
  • Salomaa, A. Formal Languages, Academic Press, 1973. (Note 9.1, pp. 90-91, discusses bijective base-k for all k ≥ 2.)
  • Smullyan, R. "Theory of Formal Systems", Annals of Mathematics Studies, Number 47, Princeton, 1961.

External links


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • bijective numeration — noun A numeral system that uses digits to establish a bijection between finite strings and the positive integers, especially by k adic notation such as unary and decimal without a zero …   Wiktionary

  • Système de numération bijectif — En mathématiques, un système de numération bijectif est un système de numération qui établit une bijection entre l ensemble des entiers naturels et l ensemble des chaînes finies de « chiffres », pris parmi un ensemble fini. En… …   Wikipédia en Français

  • Numeral system — This article is about different methods of expressing numbers with symbols. For classifying numbers in mathematics, see number system. For how numbers are expressed using words, see number names. Numeral systems by culture Hindu Arabic numerals… …   Wikipedia

  • Non-standard positional numeral systems — Numeral systems by culture Hindu Arabic numerals Western Arabic (Hindu numerals) Eastern Arabic Indian family Tamil Burmese Khmer Lao Mongolian Thai East Asian numerals Chinese Japanese Suzhou Korean Vietnamese …   Wikipedia

  • Bijection — A bijective function, f:X→Y, where set X is {1, 2, 3, 4} and set Y is {A, B, C, D}. For example, f(1) = D. A bijection (or bijective function or one to one correspondence) is a function giving an exact pairing of the elements of two… …   Wikipedia

  • Unary numeral system — The unary numeral system is the bijective base 1 numeral system. It is the simplest numeral system to represent natural numbers: in order to represent a number N , an arbitrarily chosen symbol representing 1 is repeated N times. For example,… …   Wikipedia

  • List of mathematics articles (B) — NOTOC B B spline B* algebra B* search algorithm B,C,K,W system BA model Ba space Babuška Lax Milgram theorem Baby Monster group Baby step giant step Babylonian mathematics Babylonian numerals Bach tensor Bach s algorithm Bachmann–Howard ordinal… …   Wikipedia

  • Positional notation — Numeral systems by culture Hindu Arabic numerals Western Arabic (Hindu numerals) Eastern Arabic Indian family Tamil Burmese Khmer Lao Mongolian Thai East Asian numerals Chinese Japanese Suzhou Korean Vietnamese …   Wikipedia

  • decimal without a zero — noun Bijective numeration in base ten …   Wiktionary

  • k-adic notation — noun The bijective numeration of digits 1 thru k inclusive that uses position in powers of k to encode an integers expansion …   Wiktionary

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”