n-ary and n-adic number representations
There exists a natural bijective correspondence between words over a
given alphabet 
, and the natural
numbers. Bijective means that every string should correspond to
exactly one number and every number to exactly one string.
Namely, the words can be totally ordered by letting shorter strings
come before longer ones, and when words are equally long by ordering
them alphabetically with respect to some total ordering on the
(finite) alphabet .
This total ordering defines a bijective correspondence by associating
the first string to the number 0, the second one to 1, and so on.
This bijective correspondence could be called the
straightforward enumeration of strings with respect to a
given total order on .
As we assume a total order on the alphabet ,
we can speak of the first letter, the second, etc. Let n
= || be the size of the alphabet,
and write value(x)=i when x is the ith letter.
Now it is possible to calculate the number associated with a given
string ak-1ak-2...a0, namely by means
of the formula i=0k-1
value(ai) ni.
This was the subject of homework 3.5.
One can think of the first letter as the digit 1, the second letter as
the digit 2, etc. This way they correspond with their values.
Now the word corresponding to a certain natural number is called the
n-adic representation of that number.
The n-adic number representation is a representation in base
n, just like the n-ary representation. In both
representation schemes the number associated to a string
ak-1ak-2...a0 is given by
i=0k-1
value(ai) ni.
The difference is that in the n-ary representation the values
of the digits range from 0 to n-1, and in the n-adic
representation from 1 to n.
The n-ary representation yields a unique number for every
string, but not a unique string for every number. This is due to the
number 0. In the decimal representation for instance, the strings
00587 and 587 denote the same number, because initial 0's do not count.
This representational inefficiency is eliminated by trading the digit
0 for the digit n, while still every natural number has a
representation.