2010 AMC 12B Problem 25

Attempt Problem 25 of the 2010 AMC 12B below, then check your answer against the professionally curated solution from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2010 AMC 12B solutions, or check the answer key.

All problems are used with official legal permission of the Mathematical Association of America (MAA).

25.

For every integer n2,n\ge2, let pow(n)\operatorname{pow}(n) be the largest power of the largest prime that divides n.n. For example, pow(144)=pow(2432)=32.\operatorname{pow}(144)=\operatorname{pow}(2^4\cdot3^2)=3^2. What is the largest integer mm such that 2010m2010^m divides n=25300pow(n)?\prod_{n=2}^{5300}\operatorname{pow}(n)?

7474

7575

7676

7777

7878

Answer: D
Concepts:prime factorizationprimecounting integers in a range
Difficulty rating: 2640
Solution:

Since 2010=23567,2010=2\cdot3\cdot5\cdot67, write the product as 2A3B5C67D2^A3^B5^C67^D times a factor coprime to all four primes; then m=min(A,B,C,D).m=\min(A,B,C,D).

Prime 2:2: pow(n)\operatorname{pow}(n) is a power of 22 only when n=2k.n=2^k. Since 212=4096<5300<213,2^{12}=4096\lt5300\lt2^{13}, the values k=1,,12k=1,\ldots,12 contribute A=1+2++12=78.A=1+2+\cdots+12=78.

Prime 67:67: pow(n)=67\operatorname{pow}(n)=67 when 6767 is the largest prime factor, i.e. n=67jn=67j with 1j791\le j\le79 and every prime factor of jj at most 67;67; excluding j=67,71,73,79j=67, 71, 73, 79 leaves 7575 values. The one nn with pow(n)=672\operatorname{pow}(n)=67^2 is n=672<5300,n=67^2\lt5300, adding 2.2. So D=75+2=77.D=75+2=77.

Prime 3:3: For n=2a3bn=2^a3^b with b=1,2,3,4,b=1,2,3,4, the numbers of allowable exponents aa are 11,10,8,7,11,10,8,7, respectively. These terms alone contribute B11+210+38+47=83. \begin{aligned} B&\ge11+2\cdot10 \\ &\quad+3\cdot8+4\cdot7=83. \end{aligned}

Prime 5:5: Write n=2a3c5b.n=2^a3^c5^b. For b=1,b=1, the counts over c=0,ldots,6c=0,ldots,6 total 11+9+7+6+4+3+1=41.11+9+7+6+4+3+1=41. For b=2,b=2, the counts total 8+7+5+3+2=25,8+7+5+3+2=25, each contributing two factors of 5.5. Hence C41+225=91.C\ge41+2\cdot25=91.

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

Thus, the correct answer is D.

← Problem 24#24
Full Exam

Problem 25 in Other Years