To expand on how the solution you included in your question works: Consider the powers of $2$ with $k$ digits. There are five possible sequences of first digits of these $k$-digit powers of $2$:
- $1 \to 2 \to 4 \to 8$. For instance, for $k = 1$ digit, we have $2^0 = \boldsymbol{1}$, $2^1 = \boldsymbol{2}$, $2^2 = \boldsymbol{4}$, and $2^3 = \boldsymbol{8}$.
- $1 \to 2 \to 4 \to 9$. For instance, for $k = 16$ digits, we have $2^{50} = \boldsymbol{1}125899906842624$, $2^{51} = \boldsymbol{2}251799813685248$, $2^{52} = \boldsymbol{4}503599627370496,$ and $2^{53} = \boldsymbol{9}007199254740992$.
- $1 \to 2 \to 5$. For instance, for $k = 3$ digits, we have $2^7 = \boldsymbol{1}28$, $2^8 = \boldsymbol{2}56$, and $2^9 = \boldsymbol{5}12$.
- $1 \to 3 \to 6$. For instance, for $k = 2$ digits, we have $2^4 = \boldsymbol{1}6$, $2^5 = \boldsymbol{3}2$, and $2^6 = \boldsymbol{6}4$.
- $1 \to 3 \to 7$. For instance, for $k = 14$ digits, we have $2^{44} = \boldsymbol{1}7592186044416$, $2^{45} = \boldsymbol{3}5184372088832$, and $2^{46} = \boldsymbol{7}0368744177664$.
For every number length ranging from $k = 1$ digit through $k = 603$ digits, we must see one of those five patterns. This covers all of $S$ except $2^{2004}$, which begins with a $1$.
Let $x$ be the number of patterns of length $4$ (the first two) and $y$ be the number of patterns of length $3$ (the last three). Then from the fact that there are $603$ different number lengths under consideration, we have
$$
x+y = 603
$$
From the fact that there are $2004$ powers of $2$ under consideration, and knowing that $x$ patterns are of length $4$ and $y$ patterns of length $3$, we have
$$
4x+3y = 2004
$$
Solving these yields $x = 195$ and $y = 408$. Since the patterns of length $4$ are exactly those that contain a power of $2$ with the first digit $4$, the number of such powers of $2$ is $x = 195$.
The above solution does not use the value of the log (base $10$) of $2$. Here's one way to use it: First, imagine that the log of $2$ was exactly $0.3$. Then the log of $2^2 = 4$ would be $0.6$, that of $2^3 = 8$ would be $0.9$, and so forth. The log of $10/2 = 5$ would be $1-0.3 = 0.7$. So a power of $2$ would begin with $4$ if its log had a decimal portion of $0.6$.
Since $3$ and $10$ are relatively prime, the log of every $10$ consecutive powers of $2$ would contain each of the decimal portions from $0.0$ through $0.9$ exactly once each, meaning that they would contain $0.6$ exactly once, meaning in turn that exactly one of those $10$ powers of $2$ would begin with $4$. These would be $2^2, 2^{12}, 2^{22}, \ldots, 2^{2002}, \ldots$ and the answer to our question would be $201$.
But the log of $2$ is not exactly $0.3$. A closer approximation is $0.301$. Suppose that were exact; then the log of $4$ would be $0.602$, and that of $5$ would be $1-0.301 = 0.699$. Since $301$ and $1000$ are relatively prime, the logs of every $1000$ consecutive powers of $2$ would contain each decimal portion from $0.000$ through $0.999$ exactly once each, meaning in particular that it would contain a decimal portion between $0.602$ and $0.698$ (inclusive) exactly once each, meaning in turn that there would be $698-602+1 = 97$ powers of $2$ that began with $4$. Along with $2^{2002}$, the answer to our question would be $97+97+1 = 195$.
That turns out to be the answer, but to be sure, we'd have to know the log of $2$ to more digits. Five digits is a good place to stop; the log of $2$ to five digits is $0.30103$, and that is very accurate. (The value to ten digits is $0.3010299957$.) With that value, and a bit more algebra, we can confirm the answer of $195$.
