## Systems of numeration.(English)Zbl 0568.10005

[See also Computer arithmetic, Proc. 6th. Sympos., Aarhus/Den. 1983, 37–42 (1983; Zbl 0545.10005).]
The main theorem is as follows. Let $$u_{-m+1},u_{-m+2},...,u_{-1}$$ be fixed nonnegative integers, let $$b_ 2\geq...\geq b_ m\geq 1$$ be constants and $$b_ 2\leq b_ 1=b_ 1(n)$$, and let the increasing sequence $$S=\{u_ n\}$$ be defined by $$u_ 0=1$$, $$u_ n=b_ 1(n)u_{n-1}+b_ 2u_{n-2}+...+b_ mu_{n-m}$$ $$(n\geq 1)$$. Then any nonnegative integer $$N$$ has a unique representation in the form $$N=d_ 0u_ 0+...+d_ nu_ n$$ if the $$d_ i$$ are nonnegative integers satisfying the following two-fold condition: (i) Let $$k\geq m-1$$. For any $$j$$ satisfying $$0\leq j\leq m-2$$, if $$(*) (d_ k,d_{k-1},...,d_{k- j+1})=(b_ 1(k+1),b_ 2,...,b_ j)$$ then $$d_{k-j}\leq b_{j+1}$$; and if (*) holds with $$j=m-1$$, then $$d_{k-m+1}<b_ m$$. (ii) Let $$0\leq k<m- 1$$. If (*) holds for any j satisfying $$0\leq j\leq k-1$$, then $$d_{k-j}\leq b_{j+1}$$; and if (*) holds with $$j=k$$, then $$d_ 0<\sum^{m}_{i=k+1}b_ i u_{k+1-i}$$. Known numeration systems, such as those with $$u_ n=b^ n$$ or $$u_ n=(n+1)!$$, and higher order Fibonacci systems, are derived from the theorem.

### MSC:

 11A67 Other number representations 05A05 Permutations, words, matrices

Zbl 0545.10005
Full Text:

### Online Encyclopedia of Integer Sequences:

Representation of n in base of Catalan numbers (a classic greedy version).
List of Catalan numerals.