A combinatorial interpretation of double base number system and some consequences. (English) Zbl 1178.05008

Mishra, Pradeep Kumar; Dimitrov, Vassil

Adv. Math. Commun. 2, No. 2, 159-173 (2008).

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.

Reviewer: Andreas N. Philippou (Patras)

MSC:

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

Keywords:

double base number system; DBNS; representation scheme; graphical representation of numbers; DBNS graphs; MB graphs