n-ary and n-adic number representations

There exists a natural bijective correspondence between words over a given alphabet 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 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 alphabet.

As we assume a total order on the alphabet alphabet, we can speak of the first letter, the second, etc. Let n = |alphabet| 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 alphabeti=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 alphabeti=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.

Rob van Glabbeek rvg@cs.stanford.edu