2010 AMC 12B Problem 25

Question

For every integer

n\ge2,

let

\operatorname{pow}(n)

be the largest power of the largest prime that divides

n.

For example,

\operatorname{pow}(144)=\operatorname{pow}(2^4\cdot3^2)=3^2.

What is the largest integer

m

such that

2010^m

divides

\prod_{n=2}^{5300}\operatorname{pow}(n)?

74

75

76

77

78

Answer: D

Concepts:prime factorization prime counting integers in a range

Difficulty rating: 2640

Small hint:

2010=2\cdot3\cdot5\cdot67;

find the exponent of each prime in the product and take the minimum

Big hint:

\operatorname{pow}(n)

contributes a prime

p

only when

p

is the largest prime factor of

n

Solution:

Since

2010=2\cdot3\cdot5\cdot67,

write the product as

2^A3^B5^C67^D

times a factor coprime to all four primes; then

m=\min(A,B,C,D).

Prime $2:$

\operatorname{pow}(n)

is a power of

2

only when

n=2^k.

Since

2^{12}=4096\lt5300\lt2^{13},

the values

k=1,\ldots,12

contribute

A=1+2+\cdots+12=78.

Prime $67:$

\operatorname{pow}(n)=67

when

67

is the largest prime factor, i.e.

n=67j

with

1\le j\le79

and every prime factor of

j

at most

67;

excluding

j=67, 71, 73, 79

leaves

75

values. The one

n

with

\operatorname{pow}(n)=67^2

is

n=67^2\lt5300,

adding

2.

So

D=75+2=77.

Prime $3:$ For

n=2^a3^b

with

b=1,2,3,4,

the numbers of allowable exponents

a

are

11,10,8,7,

respectively. These terms alone contribute

\begin{aligned} B&\ge11+2\cdot10 \\ &\quad+3\cdot8+4\cdot7=83. \end{aligned}

Prime $5:$ Write

n=2^a3^c5^b.

For

b=1,

the counts over

c=0,\ldots,6

total

11+9+7+6+4+3+1=41.

For

b=2,

the counts total

8+7+5+3+2=25,

each contributing two factors of

5.

Hence

C\ge41+2\cdot25=91.

Therefore

m=\min(78,B,C,77)=77.

Thus, the correct answer is D.

2010 AMC 12B Problem 25

Answer: D

Difficulty rating: 2640

Small hint:

Big hint:

Solution:

Problem 25 in other years