1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Possibly related: math.stackexchange.com/questions/1199682/… ; see also OEIS A062518. $\endgroup$ – Watson Apr 17 '17 at 13:41
  • 2
    $\begingroup$ What about $256 = (100*2^1) + (10*2^2) + (1*2^4)$? $\endgroup$ – WaveX Apr 17 '17 at 14:00
  • $\begingroup$ @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. $\endgroup$ – Connor Harris Apr 17 '17 at 14:03
  • $\begingroup$ @Connor Harris ah I see that now. I read it a little quickly. $\endgroup$ – WaveX Apr 17 '17 at 14:53
  • $\begingroup$ 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. $\endgroup$ – Misha Lavrov Apr 17 '17 at 19:52
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – N. S. Apr 18 '17 at 15:30
  • $\begingroup$ 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. $\endgroup$ – Misha Lavrov Apr 18 '17 at 15:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.