A numeration system is a triple , where is a positive integer, is a non-empty alphabet, and is a one-to-one function from to the set of non-negative integers . Order elements of so that their values are in increasing order:
, where for .
is called the base of numeration system , and the elements the digits of . Words over are called numeral words.
Given a numeral word with , the integer non-negative is said to be represented by if
An integer is said to be representable in if there is a numeral word representing .
The most common numeration system is the decimal system:
where is the identity function.
Just as common is the binary digital system: where again is the identity function.
In fact, any digital system is a numeration system , where and .
Consider the system , where . Since any word over is just a string of ’s, consecutive strings of represent . We conclude that the integers representable by have the form for any positive integer .
Consider the system
where . It is easy to see that every integer is representable by . However, some integers may be represented by more than one numeral words. For example,
The numeration system is used by the Chinese.
Consider the system where . Then . Notice that can not be represented . Also, note that .
A numeration system is said to be complete if every non-negative integer has at least one representation in ; and unambiguous if every non-negative integer has at most one representation in . is ambiguous if is not unambiguous. Every digital system is complete and unambiguous. In the examples above, is complete but ambiguous; is unambiguous but not complete; is neither complete nor unambiguous.
|Date of creation||2013-03-22 18:57:46|
|Last modified on||2013-03-22 18:57:46|
|Last modified by||CWoo (3771)|
|Defines||complete numeration system|
|Defines||unambiguous numeration system|
|Defines||ambiguous numeration system|