2004 AMC 12B Problem 25

Question

Given that

2^{2004}

is a

604

-digit number whose first digit is

1,

how many elements of the set

S = \{2^0, 2^1, 2^2, \ldots, 2^{2003}\}

have a first digit of

4?

194

195

196

197

198

Answer: B

Concepts:digits pattern recognition

Difficulty rating: 2360

Small hint:

The number of digits of

2^k

increases by

1

exactly when its leading digit forces a carry

Big hint:

A power of

2

has leading digit

8

or

9

precisely when the previous power has leading digit

4

Solution:

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.