I was watching this video on YouTube where it is told (at 6:26) that $2^{16} = 65536$ has no powers of $2$ in it when represented in base-$10$. Then he – I think as a joke – says "Go on, find another power of $2$ that doesn't have a power of $2$ digit within it. I dare you!"
So I did. 🙂 I wrote this little Python program to check for this kind of numbers:
toThePower = 0
possiblyNoPower = True
while True:
number = str(2**toThePower)
for digit in number:
if int(digit) in [1,2,4,8]:
possiblyNoPower = False
print('Not ' + number)
break
if possiblyNoPower:
print(number + ' has no digit that is a power of 2.')
toThePower += 1
possiblyNoPower = True
Sidenote: I could use the programming language Julia instead of Python, which may be much quicker, but I already checked for really big numbers and such a program (and brute-force in general) will never proof that there are no other powers of $2$ having this property. It might disprove it, but I think the chance is really really small.
I checked all the way to $2^{23826}$, which is a 7173 digit number, but no luck. Since the numbers are getting more and more digits with bigger powers of $2$, the chance of a number having no digit that is a power of $2$ becomes smaller and smaller.
I made a plot of $\frac{\text{number of digits being a power of 2}}{\text{total number of digits}}$ versus the $n$th power of $2$ on a logarithmic scale.
This graph is wrong! See the edit.
As I predicted, the graph drops really fast to almost $0$. I think that $\frac{\text{number of digits being a power of 2}}{\text{total number of digits}}\rightarrow 0$ as $n \rightarrow \infty$ and thus $\text{P}(n\text{th power of 2 having no digits of 2 in it}) \rightarrow 0$, but this is just my intuition.
So my question: Is $2^{16} = 65536$ the only power of $2$ that has no digit in it that is a power of $2$ (so no digit $\in \{1,2,4,8\}$) when represented in base-$10$? Is there a proof, a counterexample, or is it an open question? I'm also curious about powers of $2$ having no digits that are a power of $2$ in other bases than $10$.
Edit: As @Aweygan noted, the graph above is wrong. I accidentally divided by the number itself, instead of the amount of digits the number has. Below a good version, on a linear scale.
From this graph it appears that $\frac{\text{number of digits being a power of 2}}{\text{total number of digits}} \rightarrow 0.4 $ as $n \rightarrow \infty$. This seems to make sense, since $\text{P}(\text{digit} \in {1,2,4,8}) = 4/10 = 0.4$ and since the number of digits becomes larger and larger, the law of large numbers becomes "visible".
About the possible duplicate: that question was posted 4.5 years ago. The status of the problem (proven, disproven, open question) might well be changed in the maintime. 🙂
Best Answer
I believe your question is still open. Some notation before we move on to a related conjecture:
Denote $a\preceq b$ if $a$ is a subsequence of $b$ when they are both written in base $10$, e.g., $553\preceq 65536$, $63\preceq 65536$, but $35$ is not a subsequence (so order matters). Given a set $S\subseteq\mathbb{N}$, we define the minimal set as the smallest set $M\subset S$, such that for all $s\in S$, there exists $m\in M$ and $m\preceq s$. From Higman's lemma, we know that the minimal set is finite for every possible $S$.
Back to your question, there is a weaker conjecture by J. Shallit in
that $\{1,2,4,8,65536\}$ is the minmal set of powers of $2$ in base $10$, which as far as I can tell is still open. As Shallit observed in the paper that this conjecture is true if "every power of $16$ greater than $65536$ contains a digit in the set $\{1,2,4,8\}$", which is precisely your question.
For numerical search, you can take a look at $A137998$. The question is equivalent to the statement that $16^4$ is the only entry of $0$ that appears in this sequence. Due to a repeating pattern mentioned in its comments, you would only need to check at most $12$ out of every $25$ powers of $16$.
(Note this had been posted as a comment, but as it was the 10+th comment, I know that not everyone would notice it. I hope it has been expanded enough to be warranted as an answer. Please let me know if otherwise)
edited: below is taken from Shallit's paper as an attempt to make the concept of "minimal set" more accessible.
We will take a look at prime numbers. If I were to claim, as an analogy to the original question, that all prime numbers when written in base-$10$ must contain a prime digit, i.e., $\{2,3,5,7\}$, you would easily be able to find a counterexample: "How about $11$? and $19$?". However, I could expand the list to include all $2$-digit prime numbers that has no prime digit, i.e., $\{2,3,5,7,11,19,41,61,89\}$. Then I would claim that all prime numbers must contain a prime number in this new list. This is where I would need to clarify what it means by a number to "contain" another number with more than one digit, e.g., $19$. The defintion chosen here is that given a number $b$, if we can reach $a$ by deleting some digits of $b$, then we say $b$ contains $a$ (or $a\preceq b$). As an example, $109$ is a prime number and it contains $19$. This time it would take you a bit effort to find a disproof: the first one is $409$. The procedure goes on as I would extend the list to include such $3$-digit prime numbers and you would produce larger counter-examples, so on so forth.
The surprise is that this process necessarily ends, due to Higman's lemma. As my list grows longer (but remains finite), at certain point the claim becomes true. We call the final list minimal set of prime numbers.
We can repeat this process for powers of $2$, which leads to the conjecture that $\{1,2,4,8,65536\}$ is the minimal set. This is apparently weaker than your question, as it allows the possibility that there exists some power of $2$ that does not contain $1,2,4,8$ but contains $65536$. Note the proofs we know for Higman's lemma, albeit constructive, are not effective to give us the actual minimal set in general. Shallit did manage to get the answer for prime numbers using elementary means, but as far as I know, there is no progress for the minimal set of powers of $2$, which in turn indicates that the stronger statement in your question is still open.