Find all positive integers $n$ such that the binary representation of
$n$ ends with its decimal digits and contains at most two 1's in its
decimal representation.
Here is my current approach:
$$
n_{10} = \overline{a_1a_2\dots a_k}
$$
$$
n_2 = \overline{b_1b_2\dots b_l}
$$
Where $k= \lfloor \log_{10}(n) \rfloor + 1$ and $l = \lfloor \log_2(n) \rfloor + 1$.
I attempted to express this problem as:
$$
n_2 = \overline{b_1b_2 \ldots b_{\lfloor \log_2(n) \rfloor – \lfloor \log_{10}(n) \rfloor} a_1a_2 \ldots a_{\lfloor \log_{10}(n) \rfloor} a_{\lfloor \log_{10}(n) \rfloor + 1}}
$$
Writing it out, we have:
$$
a_1 \times 10^{\lfloor \log_{10}(n) \rfloor} + a_2 \times 10^{\lfloor \log_{10}(n) \rfloor – 1} + \dots + a_{\lfloor \log_{10}(n) \rfloor – 1} \times 10^1 + a_{\lfloor \log_{10}(n) \rfloor} \times 10^0
$$
$$
= b_1 \times 2^{\lfloor \log_2(n) \rfloor} + b_2 \times 2^{\lfloor \log_2(n) – 1 \rfloor} + \dots + b_{\lfloor \log_2(n) – 1 \rfloor} \times 2^1 + b_{\lfloor \log_2(n) \rfloor} \times 2^0
$$
$$
\sum_{i=0}^{\lfloor \log_{10}(n) \rfloor} a_i \times 10^i = \sum_{j=0}^{\lfloor \log_2(n) \rfloor} b_j \times 2^j
$$
From here I am thinking of constructing some sort of relation between $a_1,a_2, \ldots, a_{\lfloor \log_{10}(n) \rfloor + 1}$ and $ b_{\lfloor \log_2(n) \rfloor – \lfloor \log_{10}(n) \rfloor + 1}, \dots, b_{\lfloor \log_{2}(n) \rfloor + 1} $ to draw out some specific conditions about the $n$ that satisfy the condition.
I am not really sure however how to do this and if this is fruitful approach at all.
So any help would be greatly appreciated!
Best Answer
The binary representation of $n$ ending with the decimal digits of $n$ means those decimal digits can only be $0$ or $1$. Since $n$ can only contain up to two $1$'s in its decimal representation, and it's positive, then there are $2$ main cases to consider, as Calvin Lin's comment hint suggests.
First, $n$ has just one $1$ in its decimal representation, i.e., $n = 10^{a} = 5^{a}(2^{a})$ for some integer $a \ge 0$, which is $1$ followed by $a$ zeros in decimal. In binary, it will be the binary representation of $5^{a}$ followed by $a$ zeros. Since $5^{a}$ is odd, its last binary digit is $1$, so all such values work. Alternatively, using Calvin's suggestion, $10^{a}\equiv 2^{a}\pmod{2^{a+1}}\;\to\; 5^{a}\equiv 1\pmod{2}$ is always true. For example, as your comment indicates, $a = 1$ gives $\color{blue}{10}_{10} = 10\color{blue}{10}_{2}$.
Second, $n$ has two $1$'s in its decimal representation. Then, $n = 10^{a} + 10^{b}$ for some integers $a \gt b \ge 0$. In this case, in binary going from the right to the left, $b$ digits will be $0$, then a $1$, then $a - b - 1$ more zeros, and then a $1$. For this to happen requires that, in binary, $5^b$ ends with a $1$, but with at least $a - b$ zeros to the left of that. This means that
$$5^{b} \equiv 1 \pmod{2^{a - b + 1}} \;\;\to\;\; 2^{a - b + 1} \mid 5^{b} - 1$$
We also get this by using Calvin's suggestion of $10^{a} + 10^{b}\equiv 2^{a} + 2^{b} \pmod{2^{a+1}}$ which leads to $2^{b}(5^{b}-1)\equiv 2^{a}(1-5^{a}) \pmod{2^{a+1}} \;\to\; 5^{b}-1\equiv 2^{a-b}(1-5^{a})\equiv 0\pmod{2^{a-b+1}}$.
Note that $b = 0$ works for all values of $a$, i.e., $n = 10^a + 1$ (e.g., $\color{blue}{101}_{10} = 1100\color{blue}{101}_{2}$, as stated in Eric's comment). Otherwise, for $b \gt 0$, then using the Lifting-the-exponent lemma, if $b$ is even, we require
$$\nu_2(5^{b} - 1) = \nu_2(4) + \nu_2(6) + \nu_2(b) - 1 = 2 + \nu_2(b) \ge a - b + 1 \;\to\; \nu_2(b) \ge a - b - 1$$
For example, there's $a = 3$ and $b = 2$ with $\color{blue}{1100}_{10} = 1000100\color{blue}{1100}_{2}$, and $a = 4$ and $b = 2$ with $\color{blue}{10100}_{10} = 100111011\color{blue}{10100}_{2}$.
If $b$ is odd instead, then the condition is that
$$\nu_2(5^{b} - 1) = \nu_2(5 - 1) = 2 \ge a - b + 1$$
Since $a - b \ge 1$, the only case which works is where $a = b + 1$. For example, we have with $a = 2$ and $b = 1$ that $\color{blue}{110}_{10} = 110\color{blue}{110}_{2}$, plus $a = 4$ and $b = 3$ giving $\color{blue}{11000}_{10} = 101010111\color{blue}{11000}_{2}$.