Monday, September 24th

Problem

Prove that for at least 30% of the natural numbers $n$ from 1 to 1,000,000, $2^n$ starts with a 1.

Solution

Notice that if $2^{n}$ has one more digit in its decimal expansion than $2^{n-1}$, then it starts with a digit 1. Thus, it only suffices counting the digits on the decimal expansion of $2^n$ will give how many powers of 2 less than $2^n$ start with a 1. Therefore the density of such numbers is

$\frac{\log_{10} \left(2^n\right)}{n}=\log_{10} (2)\,,$

and since $2^{10}>10^3$, we have that $\log_{10} (2)>3/10$ and the result follows.