numeration system

A numeration system is a triple $N=(b,\mathrm{\Sigma },d)$, where $b>1$ is a positive integer, $\mathrm{\Sigma }$ is a non-empty alphabet, and $d$ is a one-to-one function from $\mathrm{\Sigma }$ to the set of non-negative integers $\mathbb{N}\cup \{0\}$. Order elements of $\mathrm{\Sigma }$ so that their values are in increasing order:

$\mathrm{\Sigma }=\{a_1,\mathrm{\dots },a_k\}$, where for $i=1,\mathrm{\dots },k-1$.

$b$ is called the base of numeration system $N$, and the elements $a_1,\mathrm{\dots },a_k$ the digits of $N$. Words over $\mathrm{\Sigma }$ are called numeral words.

Given a numeral word $u=c_1\mathrm{\cdots }{c}_m$ with $c_j\in \mathrm{\Sigma }$, the integer non-negative $n$ is said to be represented by $u$ if

$$n=c_1{b}^{m-1}+\mathrm{\cdots }+c_j{b}^{m-j}+\mathrm{\cdots }+c_m.$$

An integer $n$ is said to be representable in $N$ if there is a numeral word $u$ representing $n$.

Examples.

• The most common numeration system is the decimal system:

  $$D=(10,\{0,1,2,3,4,5,6,7,8,9\},d)$$

  where $d(i)=i$ is the identity function.

• Just as common is the binary digital system: $B=(2,\{0,1\},d)$ where $d$ again is the identity function.

• In fact, any digital system is a numeration system $(n,\mathrm{\Sigma },d)$, where $\mathrm{\Sigma }=\{a_0,\mathrm{\dots },a_{n-1}\}$ and $d(a_i)=i$.

• Consider the system $B_1=(2,\{1\},d)$, where $d(1)=1$. Since any word over $\{1\}$ is just a string of $1$’s, $n$ consecutive strings of $1$ represent $1+2+\mathrm{\cdots }+2^{n-1}=2^{n-1}$. We conclude that the integers representable by $N$ have the form $2^n-1$ for any positive integer $n$.

• Consider the system

  $$D_1=(10,\{[0],[1],\mathrm{\dots },[9],[10],[100],[1000],[10000],[10000000],[10000000000]\},d)$$

  where $d([i])=i$. It is easy to see that every integer is representable by $D_1$. However, some integers may be represented by more than one numeral words. For example,

  $$[1000]=[100][0]=[10][0][0]=[1][0][0][0].$$

  The numeration system $D_1$ is used by the Chinese.

• Consider the system $N=(3,\{[1],[2],[4]\},d)$ where $d([i])=i$. Then $[2][1][4][1]=2\times 3^3+1\times 3^2+4\times 3+1=184$. Notice that $0$ can not be represented $N$. Also, note that $[4]=4=1\times 3+1=[1][1]$.

A numeration system $N$ is said to be complete if every non-negative integer has at least one representation in $N$; and unambiguous if every non-negative integer has at most one representation in $N$. $N$ is ambiguous if $N$ is not unambiguous. Every digital system is complete and unambiguous. In the examples above, $D_1$ is complete but ambiguous; $B_1$ is unambiguous but not complete; $N$ is neither complete nor unambiguous.

Remark. Representation non-negative integers by a numeration system can be extended to rational numbers. The corresponding concepts of completeness and ambiguity may be defined similarly.