What's the number of decibinary numbers that evaluate to given decimal number? 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)$?
 A: 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.
A: Indeed, you need more than just the number of representations for a given number $n$. Here is a way to compute the table.
Let $N(d, m)$ be the number of decibinary representations of length $m$ or less decibits of the decimal value $d$. To find $N(d, m+1)$ you need to find out what are the possible values of the $m+1$-th (leading) decibit and sum up the number of possible representations starting with those digits. To achieve that, observe that the number of representations with leading digit $d_{m+1}$ is actually the number of representations of the remainder $d - d_{m+1}\cdot{}2^{m}$ with $m$ decibits, so
$$N(d, m+1) = \sum_{p=0}^{p_{\textrm{max}}}N(d-p\cdot{}2^{m}, m)$$
where $p_\textrm{max} = \min(9, \left\lfloor\frac{d}{2^m}\right\rfloor)$. Allowing $p$ to start from $0$ effectively means that $0001$ is counted as a valid 4-digit decibinary representation of $1$. This is important for the last part.
The number of 1-decibit representations is easy:
$$N(d, 1) = \begin{cases}1, \mbox{if } d < 10\\0, \mbox{otherwise}\end{cases}$$
Computing $N$ is a typical dynamic programming problem. You fill up $N(d, m)$ by iterating $d$ from $0$ to some max value $d_\textrm{max}$ and $m$ from $1$ to $\lceil\log_2{}d_\textrm{max}\rceil$. The longest representation is always the one using $0$ and $1$ only, i.e., the binary one, and its length is a monotonic function of $d$.
Finally, $f(n) = N(n, \lceil\log_2{}d_\textrm{max}\rceil)$. The space complexity of the algorithm is $O(d \log d)$. For the test cases (limited to the first $10^7$ table entries), $d_\textrm{max} = 4449$ and the table has $57850$ entries.
A: I have been trying to wrap my head over this problem for quite some time.
The HackerRank problem is just not limited to finding the number of ways in which a number can be expressed in decibinary. It also requires finding a decibinary representation at a randomly specified index based on a specific sort order.
For the number of ways a number can be expressed in decibinary, I had another approach: a number can be of the form 2k+1 or 2k.
The units digit for the decibinary representation can be 1,3,5,7,9 for numbers of form 2k+1 and 0,2,4,6,8 for numbers of form 2k.
This leaves us with 2k, 2k-2, 2k-4, 2k-6, 2k-8 respectively, which when divided by 2 (as we have shifted once place left in decibinary representation) gives k, k-1, k-2, k-3 and k-4
Hence, f(2k+1) or f(2k) = f(k) + f(k-1) + f(k-2) + f(k-3) + f(k-4); of course subject to k-1, k-2, k-3, k-4 being non-negative (in case any of them is negative, the corresponding term vanishes).
Through this, we can build the function f from ground up starting from zero, and time complexity of building the function up to n is O(n).
Here's a Python snippet:
def numDBNsTill(n):
numDBNs = []

numDBNs.append(1)
numDBNs.append(1)

for k in range(2,n+1):
    if k%2 == 0:
        l = k // 2

    if k%2 == 1:
        l = (k-1) // 2

    sum = 0
    for i in range(5):
        if i <= l:
            sum = sum + numDBNs[l-i]

    numDBNs.append(sum)

return numDBNs

