Binary signed-digit integers and the Stern diatomic sequence (Q2243886)

It is well-known that the binary representation of a positive integer \(n\) is unique; that is, there is only one way to write \[n=\sum_{j\geq 0} b_j 2^j,\quad\mbox{with}\quad b_j\in\{0,1\}.\] One can consider generalisations, in particular, by allowing the \(b_j\) to take different values. This paper considers two such generalisations and prove a relationship between them (among other properties of these representations. Firstly, if we allow \(b_j\in\{0,1,2\}\), then the representation is called a hyperbinary representation of \(n\). These representations are not unique, but for each \(n\) there are only finitely many representations. The number of hyperbinary representations of \(n\) is equal to \(s(n+1)\), where \(s\) is Stern's diatomic sequence, which is defined by \(s(0)=0\), \(s(1)=1\) and for \(n\geq 0\) by the relations \(s(2n)=s(n)\) and \(s(2n+1)=s(n)+s(n+1)\). Secondly, the authors consider the \emph{Binary Signed-Digit} (BSD) representation of \(n\), wherein one allows \(b_j\in\{1,0,-1\}\). Here, an integer \(n\) is said to be in BSD representation when \[n=\sum_{j\geq 0} b_j 2^j,\ \mbox{where}\ i\geq\lceil \log_2(n)\rceil,\ \mbox{and}\ b_j\in\{-1,0,1\}.\] Given an integer \(n\), there are an infinite number of BSD representations of \(n\), but when one restricts to a finite number of bits, say \(i\), there are only a finite number of representations. We denote by \(f(n,i)\) the number of ways to represent the integer \(n\) in BSD form on \(i\) bits. In this paper, in addition to other properties, the author shows that \(f(n,i)=s(2^i-n)\) and gives a simple \(O(\log n)\) algorithm for calculating the number of BSD representations of \(n\) based on an algorithm for calculating Stern's sequence.