Systems of numeration. (English) Zbl 0568.10005

Fraenkel, Aviezri S.

Am. Math. Mon. 92, 105-114 (1985).

[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.

Reviewer: Ian Anderson (Glasgow)

MSC:

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

Keywords:

recurrence relation with negative coefficient; representation systems; numeration systems

Citations:

Zbl 0545.10005