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.

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