What's the number of decibinary numbers that evaluate to given decimal number?

Question

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)$?

Answer 1

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.

Answer 2

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.

Answer 3

It's possible to do this problem in $O(\log x)$ time. I believe I found the best time complexity solution. I was able to achieve computing the decibinary value of $x = 10^{18}$ in 92 millis and 570,231 size memo. The other solutions are chump change; for the problem bound of $10^7$, it's calculated in 1.125 milliseconds and only 277 memo entries!!

This is done utilizing the following recurrence relation to compute the number of decibinary digits map to a given digit: \begin{align} f(n < 0) &= 0 \\ f(0) &= 1 \\ f(n) &= f(n-1) + f( \left\lfloor\frac{n}{2}\right\rfloor ) - f( \left\lfloor\frac{n-5}{2}\right\rfloor ) \end{align}

This follows the sequence $1,2,4,6,10,13,18,22,30,36,45,\cdots$.

Where $f$ defines the number of decibinary digits for a decimal $n$.

For the rest of the hackerrank problem, you can find the number of decibinary digits that equal that decimal AND of are a particular length $k$ using a similar equation. However, the number of combinations of length $k$ starts at decimal $2^k$ with $1$ combination, the combinations rise for $8 \cdot 2^k - 8$ decimals where it reaches a plateau of $5^k$ combinations for a length of $2^k + 8$, then the number of combinations falls in reverse order.

For example, here is the sequences for $k=1$ and $k=2$ (I'm zero-indexing and skipping odd elements) $$1, 2, 3, 4, 5, 5, 5, 5, 5, 4, 3, 2, 1$$

$$1, 2, 4, 6, 9, 11, 14, 16, 19, 21, 23, 24, 25, 25, 25, 25, 25, 25, 24, 23, 21, 19, 16, 14, 11, 9, 6, 4, 2, 1$$

The interesting part is in ascending (or descending) order, where it will follow $f(n)$ for $2^{k+1}$ elements, then we will subtract $f(n)$ every $2^{k+1}$ elements. E.g. $g(n, k) = f(n - 2^{k+1}) - f(n - 2 \cdot 2^{k+1}) - f(n - 3 \cdot 2^{k+1}) - \cdots$. Here's a table for $g(n, k)$ up to $28$ \begin{array}{rclllll} x, & k=& 0 & 1 & 2 & 3 & 4\\ \hline 0 &: &1 & & & & \\ 2 &: &1, &1 & & & \\ 4 &: &1, &2, &1 & & \\ 6 &: &1, &3, &2 & & \\ 8 &: &1, &4, &4, &1 & \\ 10 &: &0, &5, &6, &2 & \\ 12 &: &0, &5, &9, &4 & \\ 14 &: &0, &5, &11, &6 & \\ 16 &: &0, &5, &14, &10, &1 \\ 18 &: &0, &5, &16, &13, &2 \\ 20 &: &0, &4, &19, &18, &4 \\ 22 &: &0, &3, &21, &22, &6 \\ 24 &: &0, &2, &23, &29, &10 \\ 26 &: &0, &1, &24, &34, &13 \\ 28 &: &0, &0, &25, &41, &18 \\ \end{array}

Here's the sequence for $k = 2$. Note we are only showing even indices, so the sequence is halved in size (odd indices are the same) \begin{array}{rcllllllllllll} f(n) &= & 1, &2, &4, &6, &10, &13, &18, &22, &30, &36, &45, &52 \\ f(n - 2^{k}) &= &0, &0, &0, &0, &1, &2, &4, &6, &10, &13, &18, &22 \\ f(n - 2 \cdot 2^{k}) &= &0, &0, &0, &0, &0, &0, &0, &0, &1, &2, &4, &6 \\ g(n) &= &1,&2,&4,&6,&9,&11,&14,&16,&19,&21,&23,&24 \end{array}

However, we can also note that we increase from $1$ the same amount we subtract from $5^k$, allowing us to make at most two lookups in $f$ for a given index given that the first half of the ascending portion is reflected in the second half of the ascending portion. Denote $f'(n)$ as the function that splits $f(n)$ into two portions, one where we subtract from $f(n)$ and the other where we subtract from $5^k$

\begin{array}{rcllllllllllll} f'(n) &= & 1, &2, &4, &6, &10, &13, &18, &22, &25, &25, &25, &25 \\ f(n - 2^{k}) &= &0, &0, &0, &0, &1, &2, &4, &6, &0,&0,&0,&0\\ f(8\cdot(2^k - 1) - n) &= &0,&0,&0,&0,&0,&0,&0,&0,&6, &4, &2, &1 \\ g(n, k) &= &1,&2,&4,&6,&9,&11,&14,&16,&19,&21,&23,&24 \end{array} Using this method we can produce $g(n, k)$ with at most $3$ lookups in $f$. This is easily verified by looking at the maximum length of $f$ compared to $2^{k+1}$

Now, you have the decimal for $x$ and the size of $x$. Now we find the first digit. Subtract the first digit from our decimal and recurse, finding the next leading digit. Note that subtracting the first digit from the decimal follows the same decibinary pattern so the recursion works out. Multiply the leading digit we removed by $10^k$, and add to the result we get from the recursion.

Main idea: continually get closer to our desired target index $x$ by incrementing our current index by a factor of $O(2^x)$, honing on the desired digits.

Note that for future lookups, we can also store the accumulated value of $f$ in a separate memo, then perform a binary search to quickly find the correct decimal for $x$ in $O(\log(\log(x))$ time

Answer 4

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