Bijective numeration

Encyclopedia : B : BI : BIJ : Bijective numeration

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 (k ≥ 1) to encode the integer's expansion in powers of k. (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

1 Definition
2 Properties of bijective base-''k'' numerals
3 Examples
4 The bijective base-10 system
5 Historical notes
6 References
7 External links

Definition

Bijective base-k numeration uses the digit-set (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

:a_na_n−1 ... a₁a₀

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

The digit-string representing the integer m > 0 is

:a_na_n−1 ... a₁a₀

where

:a₀ = m − q₀ k, q₀ = f(m/k);

:a₁ = q₀ − q₁ k, q₁ = f(q₀/k);

:a₂ = q₁ − q₂ k, q₂ = f(q₁/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).

Properties of bijective base-k numerals

For a given k ≥ 1,

there are exactly kⁿ bijective base-k numerals of length n ≥ 0;

a list of bijective base-k 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 bijective base-1, base-2 and base-3 numerals are as follows (with the ordinary decimal representations 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 ...

Examples

34152(five-adic) = 3×5⁴ + 4×5³ + 1×5² + 5×5¹ + 2×5⁰ = 2427(decimal).

119A(ten-adic) = 1×10³ + 1×10² + 9×10¹ + 10×10⁰ = 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 .

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 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, 20 1A, 100 9A, 101 A1, 302 2A2, 1000 99A, 1110 AAA, 2010 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.

Decimal without a zero is a simple system for counting and basic arithmetic on the positive integers, but is clearly unsuited for calculations involving zero (for which there is no digit). Also, it can be confusing if extended to represent decimal fractions. Representations are then no longer unique: the number 2, in addition to its standard representation as 2, gains another representation as 1.A, one and ten tenths (and yet others as 1.9A, 1.99A, etcetera). Furthermore, the conventional 41/20 = 2.05 comes out as 41/1A = 1.A5 (one unit plus ten tenths plus five hundredths), looking as if it could be less than two; the system also has problems presenting vulgar fractions less than a tenth, except as ratios.

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. 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. (He seems to have rediscovered this system himself, unaware of the existing literature.)

References

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

External links

From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.