Let's define a decibinary number system, where each bit (or digit) can range from $0$ to $9$, but it's place value corresponds to the one in the binary system. For example:
$$(2020)_{decibinary} = 2 \times 2^3 + 0 \times 2^2 + 2 \times 2^1 + 0 \times 2^0 = 16 + 2 = (18)_{10}$$
Note, that many decibinary numbers can evaluate to the same decimal value, e.g.
$$(1220)_{decibinary} = 1 \times 2^3 + 2 \times 2^2 + 2 \times 2^1 + 0 \times 2^0 = 8 + 8 + 2 = (18)_{10}$$
I am looking for an expression (say function $f$) or an efficient algorithm, that, given a decimal number $n$, gives me a number of decibinary numbers that evaluate to $n$. Of course I am treating e.g. $(05)_{decibinary}$ the same as $(5)_{decibinary}$ (leading zeros do not matter).
As an aside, I found the concept of decibinary numbers in this HackerRank question, where I thought it might actually be useful to be able to quickly compute $f(n)$ to solve the problem efficiently.
$$\\$$
Below are my thoughts and approaches to tackle the problem. What I tried was to first see if there is a pattern:
$$f(0) = 1 \\ f(1) = 1 \\ f(2) = 2 \\ f(3) = 2 \\ f(4) = 4 \\ f(5) = 4 \\ f(6) = 6 \\ f(7) = 6 \\ f(8) = 10 \\ f(9) = 10 \\ f(10) = 13$$
but $10$ seems to break the pattern, as there are (if I didn't skip anything) $13$ decibinary numbers that evaluate to $(10)_{10}$: $18, 26, 34, 42, 50, 106, 114, 122, 130, 202, 210, 1002, 1010$ (if it was $14$ I could see some pattern, but unfortunately $10$ cannot be encoded using one digit in decibinary).
What I spotted, however, is that I could recursively calculate $f$ (or use dynamic programming to build up a lookup table bottom-up in order to be able to reuse the computations). For instance, I know that the decibinary number evaluating to $10$ will have at max. $4$ digits (because $(10000)_{decibinary}$ already evaluates to $16$). So I can represent $f(10)$ as a sum of the number of ways I can encode $10$ using $4, 3, 2$ and $1$ digit (the latter being $0$ as there is no way I can represent $10$ using 1 digit).
Let's try to compute the number of ways to represent $(10)_{10}$ using $b=4$ digits: The first leading digit can only be $1$ ($1 \times 2^3$), and then, the remaining digits need to evaluate to $10 – 8 = 2$ and we can use the lookup: $f(2) = 2$. Using $b=3$ digits we can use $1$ and $2$ as non-zero leading digits: $1$ will require a lookup $f(6)$ and $2$ will require a lookup of $f(2)$, giving a sum of $6 + 2 = 8$ which is false (there are only $6$ ways to encode $10$ using $b=3$ bits) because $6$ itself can be encoded using $b=3$ bits and here I am considering two representations two times instead of one (if this makes sense).
It seems to me like the lookup needs to be built such that it does not store $f(n)$ but $f(n, b)$, i.e. the number of ways to encode $(n)_{10}$ in decibinary using $b$ bits (without a leading zero), which already seems like quite a complex (and inefficient) approach to me. Also each time I'd need to perform a check for a minimum number of bits needed to encode a number (e.g. $10$ cannot be encoded using $b=1$).
What are your thoughts? Is there a neat and a simple way to find $f(n)$?
Best Answer
You can use generating functions for this. The generating function for decibinary numbers is
\begin{eqnarray} \prod_{k=0}^\infty\sum_{j=0}^9x^{2^kj}=\prod_{k=0}^\infty\frac{1-x^{10\cdot2^k}}{1-x^{2^k}}\;. \end{eqnarray}
The number of ways to represent $n$ as a decibinary number is the coefficient of $x^n$ in this generating function. For instance, for decibinary numbers with up to $4$ digits, we can truncate the product at $k=3$ and let Wolfram|Alpha compute the expansion:
$$ 1 + x + 2 x^2 + 2 x^3 + 4 x^4 + 4 x^5 + 6 x^6 + 6 x^7 + 10 x^8 + 10 x^9 + 13 x^{10} + \cdots\;,$$
in agreement with your counts.