From Wikipedia, the free encyclopedia

Numeral systems by culture
Hindu-Arabic numerals
Western Arabic Eastern Arabic Khmer	Indian family Brahmi Thai
East Asian numerals
Chinese Japanese	Korean
Alphabetic numerals
Abjad Armenian Cyrillic Ge'ez	Hebrew Ionian/Greek Sanskrit
Other systems
Attic Etruscan Urnfield Roman	Babylonian Egyptian Mayan
List of numeral system topics
Positional systems by base
Decimal (10)
2, 4, 8, 16, 32, 64
3, 9, 12, 24, 30, 36, 60, more…
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. (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

Bijective base-k numeration 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

a_na_n−1 ... a₁a₀

is

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

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

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

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

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

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