# zbMATH — the first resource for mathematics

A combinatorial interpretation of double base number system and some consequences. (English) Zbl 1178.05008
A non-standard number system, called double base number system (DBNS) [V. S. Dimitrov, G. A. Jullien and W. C. Miller, “Theory and applications of the double-base number system”, IEEE Trans. Comput. 48, 1098–1106 (1999)], has recently found several applications in Signal Processing and Cryptography. The authors use DBNS graphs to prove the following recurrence relation for the number of DBNS representations $$P_s(n)$$ of any positive integer $$n$$ using the bases 2 and $$s$$: $$P_s(1)=1$$, and, for $$n>1$$, $P_s(n) = \begin{cases} P_s(n-1) + P_s(n/s)\quad&\text{if }s \mid n,\\ P_s(n-1)&\text{otherwise.}\end{cases}$ They also generalize this result to more than two bases.

##### MSC:
 94A60 Cryptography 05C20 Directed graphs (digraphs), tournaments 05C90 Applications of graph theory 11A63 Radix representation; digital problems
Full Text: