2010 AMC 12B Problems/Problem 25

Problem 25

For every integer $n\ge2$ , let $\text{pow}(n)$ be the largest power of the largest prime that divides $n$ . For example $\text{pow}(144)=\text{pow}(2^4\cdot3^2)=3^2$ . What is the largest integer $m$ such that $2010^m$ divides

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

$\textbf{(A)}\ 74 \qquad \textbf{(B)}\ 75 \qquad \textbf{(C)}\ 76 \qquad \textbf{(D)}\ 77 \qquad \textbf{(E)}\ 78$

Solution

WARNING: THIS IS A SOMEWHAT TIME-CONSUMING METHOD. IF SOMEONE HAS A MORE ELEGANT SOLUTION, PLEASE POST IT. Because 67 is the largest prime factor of 2010, it means that in the prime factorization of $\prod_{n=2}^{5300}\text{pow}(n)$ , there'll be $p_1 ^{e_1} \cdot p_2 ^{e_2} \cdot .... 67^x ...$ where $x$ is the desired value we are looking for. Thus, to find this answer, we need to look for the number of times 67 would be incorporated into the giant product. We can consider several cases.

Case 1: $p_1 \cdot 67$

$p$ can be any prime from 2 to 67. Listing all the primes and enumerating them (from 2 to 67) yields 19 primes. This results in $19 + 1 = 20$ times where 67 is counted in in the form $p_1 \cdot 67$ .

Case 2: $p_1 ^{e_1} \cdot 67$

$p$ again can be any prime from 2 to 67. Looking at $\lfloor{\frac{5300}{67}}\rfloor = 79$ helps show whether or not the number multiplied by 67 is larger than 5300. $2^{x}$ must be less than 76. This gives from $2^2$ to $2^6$ , $3^2$ and $3^3$ , $5^2$ , and $7^2$ , $11^2$ , ... $67^2$ , totaling 20.

Case 3: $p_1 \cdot p_2 ... \cdot 67$

$p$ could theoretically be any prime. 2 can pair with any prime from 3 to 37, totaling 11 primes. 3 can pair with any prime from 5 to 23, totaling 7 primes. 5 can pair with any prime from 7 to 13, totaling 3. These, altogether, sum to 21.

Case 4: $p_1 ^ {e_1} \cdot p_2 ^ {e_2} \cdot ... 67$

$p$ 's combination with any other number cannot exceed 76, that is the general rule. For example, for 2, $2^2 \cdot 3, 2^3 \cdot 3, 2^4 \cdot 3, 2^2 \cdot 5, 2^3 \cdot 5, 2^2 \cdot 7, 2^3 \cdot 7, 2^2 \cdot 11, 2^2 \cdot 13, 2^2 \cdot 17,$ and $2^2 \cdot 19.$ (Alternatively, a speedier method would have been to isolate $2^2$ , find the lowest and highest primes, and count much quicker). Repeating the same process for $3^{e_2}$ and $5^{e_3}$ quickly arrives at 3 and 2, respectively. Adding these all together yields 16.

Adding all these numbers, $20 + 20 + 21 + 16 = \boxed{77} \Rightarrow D$

Page

Toolbox

Search

2010 AMC 12B Problems/Problem 25

Problem 25

Solution