## Powers of 2 are all you need

Posted on: July 26th, 2013 by
1

Show that given any combination of digits, one can find a number 2^n that starts with the given combination of digits.

#### One Response to Powers of 2 are all you need

Let the number given be $a$. If $a$ itself is a power of 2, nothing more to be done. Else, we need to show that there exists some $k$ such that there exists a power of 2 between $a*10^k$ and $(a+1)*10^k - 1$. Taking log to the base 2, we need to show that there is some $k$ such that there exists an integer between $k \log(10) + \log(a)$ and $\log(10^k*(a+1)-1)$. The gap between these two numbers is an increasing function of $k$ and so is lower bounded by the value when $k=1$. If the fractional part of the first number $k \log(10) + \log(a)$ is less than this lower bound, the interval must include an integer. But this follows from the denseness of the fractional part of $k \log(10)$ since $\log_2(10)$ is irrational (the proof of this was part of another recent puzzle post also from Russian Olympiad).