We use the fact that for any $d \ge 1$, there exists exactly one $d$-digit power of 2 whose leading digit is 1. Since $\log_{10} 2 > 0.3$ (approx. 0.301), $2^{1000000}$ has approximately 301000 digits, so there are at least 301000 values $n$ for which $2^n$ has leading digit 1.

Huh, it's like Bedford's Law.