| Bijective Numeration |
Shopping Numeration |
Information AboutBijective Numeration |
| CATEGORIES ABOUT BIJECTIVE NUMERATION | |
| numeration | |
| non-standard positional numeral systems | |
| SHOPPER'S DELIGHT | |
|
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 .) DEFINITION ''Bijective base-k numeration'' uses the digit-set { 1, 2, ..., ''k''} (''k'' ≥ 1) to uniquely represent every non-negative integer, as follows:
::''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.
::''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 ). PROPERTIES OF BIJECTIVE BASE-''K'' NUMERALS For a given ''k'' ≥ 1,
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 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 Integer s 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 s 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
EXTERNAL LINKS
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||