Choose any natural number $x$ and let it has $y$ digits in the demical system. Then, is there a natural number $z$ where the first $y$ numbers of $2^z$ are $x$?

For example, if we let $x=20$, then the answer is 'yes' because $2^{11}=2048$ and $20$ was appeared.

What will be the result if we generalize this problem to any number systems, not only demical system? (ex. binary system, etc...)


Sure. Fix your block $N$. Then for each $k$ The greatest power of $2$ which which does not exceed $N\times 10^k$ is $$\lfloor \log_2 N\times 10^k\rfloor = \lfloor \log_2 N + k\log_2 10\rfloor$$ We note that $N\times 10^k$ ends in $k$ zeroes, so we can add $10^{k}-1$ to it without changing the first block of $N$. Thus we want to find a power of $2$ between $N\times 10^k$ and $(N+1)\times 10^k-1$ (Note: we can drop the $-1$ because $(N+1)\times 10^k$ is clearly not a power of $2$, unless $k=0$). It follows that we want to find $k$ such that $$\lfloor \log_2 N + k\log_2 10\rfloor<\lfloor \log_2 (N+1) + k\log_2 10\rfloor$$ As the $\log_2 10$ is irrational, the integer multiples of it are dense $\pmod 1$ so this is always possible.

Example: $N=7$. We can't take $k=0$, because that $-1$ interferes. If we require $k>0$ we search numerically and find that the first time these two floors are unequal comes when $k=13$. In that case we see that the left hand is $45$ and the right is $46$. Thus we are lead to expect that $2^{46}$ should begin with $7$ and indeed $2^{46}=70368744177664$.

To generalize to other bases: Note that we depend critically on the irrationality of $\log_2 10$. Indeed, $\log_{10}10 $ is rational and no power of $10$ begins with $3$. But this irrationality is enough.

  • $\begingroup$ Oh, this problem can be generalized to power of w, not only power of 2. Thank you $\endgroup$ – suliman Jan 26 '17 at 16:35

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.