For any $n$ there's a power of $2$ which contains $n$

Question

So I saw this problem in an Olympiad book, "Prove that for any natural number $n$, there exists a power of $2$ which contains $n$ in it. "

For example, $n=19$ is in $2^{13}=8192$, $n=24$ is in $2^{10}=1024$.

I tried solving it by Pigeonhole principle, but haven't made any progress. Any ideas?

Answer 1

Here's a quick sketch of a proof:

1. Prove $\log_{10}(2)$ is irrational.

2. Prove that the fractional part of $n\alpha$, where $n \in \mathbb{N}$ and $\alpha$ is irrational, is dense in $(0,1)$

3. Note that the fractional part of $\log(x)$ determines the first few digits, and then use the density of the fractional part of $n\alpha$ to prove that the first few digits of the number can be any $m \in \mathbb{N}$.

If you need more help, just ask!