# How many powers of $2$ have only $0$ or powers of $2$ as digits?

I found this question about a family of identities in which the sum of some powers of $2$, selected in a certain pattern and multiplied by powers of $10$, gives another power of $2$. These identities hinge on the fact that some powers of $2$ can be written as sums of other powers of $2$ times powers of $10$—for example, $128 = (100 \times 2^0) + (10 \times 2^1) + (1 \times 2^3)$. The accepted answer to that question considers identities that require no powers of $2$ greater than $2^3$, and no repeated powers of $10$—that is, identities resulting from powers of $2$ whose base-$10$ representation contains only the digits $\{0, 1, 2, 4, 8\}$.

How many such powers of $2$ are there? A computer search up to $2^{10^5}$ gives only seven: $\{1, 2, 4, 8, 128, 1024, 2048\}$. And I can make a heuristic argument that there shouldn't be many: $2^n$ has $\lfloor n \log_{10} 2 + 1 \rfloor$ digits, and if the digits are uniformly distributed (false for the first and last digits, but plausible for the others), the chance that a random $k$-digit number uses only the $5$ digits $\{0, 1, 2, 4, 8\}$ is $(1/2)^k$ (more properly $(4/9) (1/2)^{k-1}$, as the first digit can't be $0$, but for a rough approximation, this doesn't matter). So one expects about $\sum_{n=0}^\infty (1/2)^{n \log_2 10} = \sum_{n=0}^\infty 0.8812^n = 5.3099$ such powers of $2$.

But of course, $\text{heuristic} + \text{computer search} \neq \text{proof}$. Other questions on the digits of powers of 2 turn up a lot of unanswered, difficult-seeming conjectures. Is there any simple proof that the set of powers of $2$ with only $0$ or powers of $2$ as digits is finite—or better yet, that it contains no elements greater than $2048$?

• Possibly related: math.stackexchange.com/questions/1199682/… ; see also OEIS A062518. Apr 17, 2017 at 13:41
• What about $256 = (100*2^1) + (10*2^2) + (1*2^4)$? Apr 17, 2017 at 14:00
• @WaveX there are plenty of other identities, but I'm asking specifically about the identities that don't require powers of $2$ greater than $2^3$. That is an interesting subsidiary question, though. Apr 17, 2017 at 14:03
• @Connor Harris ah I see that now. I read it a little quickly. Apr 17, 2017 at 14:53
• Some provable assertions along these lines: there are no powers of $2$ (past $2^0$) using only the digits $\{0,1,3,5,7,9\}$, by looking at $2^n \bmod {10}$, and no powers of $2$ past $2^1$ using only the digits $\{0,2,6\}$, by looking at $2^n \bmod {100}$. It doesn't look like we'll be able to get the set $\{0,1,2,4,8\}$ in this way. Apr 17, 2017 at 19:52

This problem is unlikely to have a simple proof, because the following holds:

Theorem. For any $k$, there exists a power of $2$ whose first $k$ digits and last $k$ digits are all either $1$ or $2$.

Proof. We begin with looking at the last digits, taking $2^n \bmod 10^k$. For sufficiently large $n$, $2^n \equiv 0 \pmod{2^k}$. Since $2$ is a primitive root modulo $5$ and modulo $5^2$, it is a primitive root modulo $5^k$ for any $k$ (Wikipedia), so we can have $2^n \equiv b \pmod{10^k}$ for any $b$ such that $b \equiv 0 \pmod{2^k}$.

This is possible to accomplish with only $1$ and $2$ as digits. We start with $b_1=2$ for $k=1$, and extend $b_{k-1} \equiv 0 \pmod{2^{k-1}}$ to $b_k \equiv 0 \pmod{2^k}$ by the rule:

• If $b_{k-1} \equiv 0 \pmod{2^k}$, take $b_k = 2\cdot 10^{k-1} + b_{k-1}$.
• If $b_{k-1} \equiv 2^{k-1} \pmod {2^k}$, take $b_k = 10^{k-1} + b_{k-1}$.

(This works because $10^{k-1} \equiv 2^{k-1} \pmod 2^k$.)

There is a unique sequence of digits ending $\dots211111212122112$ that we obtain in this way; reversed, it is A023396 in the OEIS.

To make sure that $2^n$ ends in $b_k$, there will be some condition along the lines of $$n \equiv c \pmod{\phi(5^k)}$$ or $n = c + n' \phi(5^k)$ for some $n'$. From there, getting the first $k$ digits to be $1$ or $2$ is easy along the lines of a recently popular question. We might as well aim for the sequence $\smash{\underbrace{111\dots111}_k}$, because we can. To do this, we want $$\log_{10} 1.11\dots1 < \left\{\left(c + n' \cdot \phi(5^k)\right)\log_{10} 2\right\} < \log_{10} 1.11\dots2$$ where $\{x\}$ denotes the fractional part of $x$. This translates into a condition of the form $$\{n \cdot \log_{10} 2^{\phi(5^k)}\} \in I_k$$ for some interval $I_k$, which we know is possible because $\alpha = \log_{10} 2^{\phi(5^k)}$ is irrational, and therefore the sequence $\{\alpha\}, \{2\alpha\}, \{3\alpha\}, \dots$ is dense in $[0,1]$.

This concludes the proof.

Instead of the digits $\{1,2\}$ we could have used the digits $\{1,4\}$ or $\{1,8\}$ and given a similar proof; if we multiply the solution to one of these by $2$ or $4$, we get a power of $2$ whose first and last digits come from the set $\{2,4\}$ or $\{2,8\}$ or $\{4,8\}$. (We can't do this with just the set $\{0,1\}$ or $\{0,2\}$ or $\{0,4\}$ or $\{0,8\}$, because eventually we can rule these out by a modular condition.)

It's of course still almost certain that there's no large power of $2$ entirely made from the digits $\{0,1,2,4,8\}$, but you'd have to say something about the "middle digits" of such a power, which is much harder.

• For the first Theorem, $\log_{10}(2) \in \mathbb Q$ together with Dirichclet Theorem on the density of $m \log_{10}(2) +n$ imply that for any natural number $k$ there exists infinitely many powers of $2$ starting with $k$. Apr 18, 2017 at 15:30
• We have to be more careful than that, because we want this to happen at the same time as the last digits match up - so we check $\log_{10} 2^{\phi(5^k)} \notin \mathbb Q$ instead of $\log_{10} 2 \notin \mathbb Q$. But yeah, that's the idea. Apr 18, 2017 at 15:33