16
$\begingroup$

How many $N$ of the form $2^n,\text{ with } n \in \mathbb{N}$ are there such that no digit is a power of $2$?

For this one the answer given is the $2^{16}$, but how could we prove that that this is the only possible solution? and what about the general case of $x^n, \text{ with } x,n \in \mathbb{N}$?

  • 0
    Since we cannot use the digits $1,2,4$ and $8$, such numbers are unlikely. My guess is $65536$ is the only one, now to find a proof. For general $x$, it is reasonable that there are only a finite number. No matter what, we at least cannot use the digit $1$, and if I take the power high enough it seems conceivable that I have to have a $1$ somewhere. (The density of numbers without $1$'s is zero) But this is just a heuristic.2012-01-02
  • 0
    A quick brute force checks says there are no solutions below $2^{100000}$ except $2^{16}=65536$.2012-01-02
  • 1
    @Ilmari:Yes, but the question is how to prove that conclusively.2012-01-02
  • 2
    The last n digits in a sequence of powers of 2 will form a repeating cycle eventually, so if a brute force of all possible last 5 digits of powers of 2 finds only 65536, then it will be known that all possible solutions end in 65536.2012-01-02
  • 1
    We could extend Angela Richardson's idea by checking the last 6 digits of the number and finding the cycle. This could easily be done by computer. I see the contest-math tag though. No idea how you'd do this without a computer.2012-01-02
  • 1
    2^12506= 64 mod(10^6)2012-01-02
  • 1
    @Angela: I counted 76 different 5-digit endings of powers of 2 that don't contain 1, 2, 4, or 8 (the cycle length is 2500).2012-01-02
  • 2
    I think there are some unsolved problems nearby. For example, I think it has not been proved that for all sufficiently large $n$ there's a zero in the decimal representation of $2^n$. According to http://blog.tanyakhovanova.com/?p=311 it's conjectured that 86 is the highest power of 2 with no zero.2012-01-02
  • 0
    $2^n$ has about $n \log_{10}(2)$ decimal digits, and heuristically it seems reasonable that (except for the first and last few) each has approximately "probability" $6/10$ of being $0,3,5,6,7$ or $9$, so the probability that $2^n$ is a solution is approximately $(6/10)^{n \log_{10}(2)} \approx 0.857^n$. The expected number of solutions for $n \ge 17$ is then about $0.857^{17}/(1 - 0.857) = 0.514$. So it would be not at all surprising if there are none.2012-02-03
  • 1
    It is just a small simplification - but by looking at what happens mod 10 you should realise that we only need to look at powers of 16.2012-02-03

1 Answers 1