2004 AMC 12B Problem 25

The smallest power of $2$ with any given digit-count lies between $10^k$ and $2\cdot10^k,$ so it has leading digit $1.$ Because $2^{2004}$ is a $604$-digit number beginning with $1,$ it is the first $604$-digit power. Thus the powers in $S$ contain exactly one leading-$1$ number for each digit-count from $1$ through $603,$ or $603$ in all. After each leading-$1$ power, the next power leads with $2$ or $3,$ and the following power leads with $4, 5, 6,$ or $7.$ Hence $603$ elements lead with $2$ or $3,$ another $603$ lead with $4$ through $7,$ and the remaining $2004 - 3(603) = 195$ lead with $8$ or $9.$ Finally, halving a power that leads with $8$ or $9$ produces the preceding power with leading digit $4,$ and doubling any leading-$4$ power reverses this. This is a bijection, so there are $195$ elements with first digit $4.$ Thus, the correct answer is B.