37
$\begingroup$

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.

enter image description here

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.

enter image description here

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. :)

$\endgroup$
  • 3
    $\begingroup$ The last $k$ digits of $2^n$ repeat with a period $4\cdot 5^{k-1}$. I suspect if you check the repeats of the last seven or eight digits you can prove that there is always a $1,2,4,8$ in there. Your program is probably easy to modify to do that. $\endgroup$ – Ross Millikan Jul 27 '16 at 23:49
  • 1
    $\begingroup$ Shouldn't $4=2^2$ and $8=2^3$ have a value of $1$ in the plot you show? $\endgroup$ – Aweygan Jul 27 '16 at 23:50
  • 2
    $\begingroup$ The real point is to view the "middle" digits as random. Each digit has a $\frac 6{10}$ chance of not being a power of two, so if the number has $k$ digits you would say the chance of not having a power of two in it is something like $(\frac 6{10})^k$, which gets small quickly. If you haven't found one yet, the chance that there is one is very small. Of course, that is not a proof. $\endgroup$ – Ross Millikan Jul 28 '16 at 0:21
  • 4
    $\begingroup$ Note that you only need to check powers of $16$ (as other powers of $2$ end in $2,4$ or $8$). And every increase in the exponent adds at least one digit to the representation. $\endgroup$ – Joffan Jul 28 '16 at 0:40
  • 2
    $\begingroup$ Possible duplicate of How many $N$ of the form $2^n$ are there such that no digit is a power of $2$? $\endgroup$ – TonyK Aug 6 '16 at 22:29
11
+50
$\begingroup$

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

Minimal Primes, J. Recreational Math. 30 (2000), 113-117

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.

$\endgroup$
  • $\begingroup$ Are you sure "$63\preceq 65536$" ? I think according to your definition, this is typo. $\endgroup$ – rajb245 Aug 2 '16 at 18:10
  • $\begingroup$ @rajb245, it's not a typo. We can reach $63$ by deleting the two $5$'s and the $6$ at the end. For details, take a look at the links above of Higman's lemma, or Shallit's paper, or here and here $\endgroup$ – Wiley Aug 2 '16 at 18:26
  • $\begingroup$ Okay, the definition is cleared up, thank you. $\endgroup$ – rajb245 Aug 2 '16 at 18:31
  • $\begingroup$ Thanks for your expanded answer. I'll give you the bounty since it ends tomorrow. I have a few questions, it would be awesome if you could answer them. Is the set $S $ a set of digits and $s \in S$ one of those digits? Could you explain "Denote ... possible $S $ in an informal way, possible with a concrete example? And what does a minimal set of powers mean? Thanks in advance! $\endgroup$ – Kevin Aug 4 '16 at 20:46
  • $\begingroup$ @Kevin, I have added some explanation at the end. Let me now if it helps. $\endgroup$ – Wiley Aug 6 '16 at 21:52

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.