Added to Favorites

Related Searches

Definitions

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 10^{2}.) 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.

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

- a
_{n}a_{n−1}... a_{1}a_{0}

- is

- a
_{n}k^{n}+ a_{n−1}k^{n−1}+ ... + a_{1}k^{1}+ a_{0}k^{0}.

- The digit-string representing the integer m > 0 is

- a
_{n}a_{n−1}... a_{1}a_{0}

- where

- a
_{0}= m − q_{0}k, q_{0}= f(m/k);

- a
_{1}= q_{0}− q_{1}k, q_{1}= f(q_{0}/k);

- a
_{2}= q_{1}− q_{2}k, q_{2}= f(q_{1}/k);

- ...

- a
_{n}= q_{n−1}− 0 k, q_{n}= f(q_{n−1}/k) = 0;

- and

- f(x) = ceil(x) − 1,

- ceil(x) being the least integer not less than x (the ceiling function).

For a given k ≥ 1,

- there are exactly k
^{n}k-adic numerals of length n ≥ 0; - 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 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
| ... |

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
| ... |

- (34152)
_{five-adic}= 3×5^{4}+ 4×5^{3}+ 1×5^{2}+ 5×5^{1}+ 2×5^{0}= (2427)_{decimal}.

- (119A)
_{ten-adic}= 1×10^{3}+ 1×10^{2}+ 9×10^{1}+ 10×10^{0}= (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 is also known as decimal without a zero. It is a base ten positional numeral system which 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 which use a zero need to 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 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.)

- 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.

- Forslund, R. R.: "A logical alternative to the existing positional number system", Southwest Journal of Pure and Applied Mathematics, Volume 1 (September 1995), pp. 27-29. (Also available as plain text)
- Giovanni Fraterno (Italian)

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Wednesday September 10, 2008 at 11:14:06 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Wednesday September 10, 2008 at 11:14:06 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2014 Dictionary.com, LLC. All rights reserved.