Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2010 AMC 12B Problems/Problem 25"
(→‎Solution)
Line 13: Line 13:
  
 
== Solution ==
 
== 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 <math>\prod_{n=2}^{5300}\text{pow}(n)</math>, there'll be <math>p_1 ^{e_1} \cdot p_2 ^{e_2} \cdot .... 67^x ...</math> where <math>x</math> 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:'''
 +
<math>p_1 \cdot 67</math>
 +
 
 +
<math>p</math> 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 <math>19 + 1 = 20</math> times where 67 is counted in in the form <math>p_1 \cdot 67</math>.
 +
 
 +
 
 +
'''Case 2:'''
 +
<math>p_1 ^{e_1} \cdot 67</math>
 +
 
 +
<math>p</math> again can be any prime from 2 to 67. Looking at <math>\lfloor{\frac{5300}{67}}\rfloor = 79</math> helps show whether or not the number multiplied by 67 is larger than 5300. <math>2^{x}</math> must be less than 76. This gives from <math>2^2</math> to <math>2^6</math>, <math>3^2</math> and <math>3^3</math>, <math>5^2</math>,  and <math>7^2</math>, <math>11^2</math>, ... <math>67^2</math>, totaling 20.
 +
 
 +
'''Case 3:'''
 +
<math>p_1 \cdot p_2 ... \cdot 67</math>
 +
 
 +
<math>p</math> 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:'''
 +
<math>p_1 ^ {e_1} \cdot p_2 ^ {e_2} \cdot ... 67</math>
 +
 
 +
<math>p</math>'s combination with any other number cannot exceed 76, that is the general rule.
 +
For example, for 2, <math>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,</math> and <math>2^2 \cdot 19.</math> (Alternatively, a speedier method would have been to isolate <math>2^2</math>, find the lowest and highest primes, and count much quicker). Repeating the same process for <math>3^{e_2}</math> and <math>5^{e_3}</math> quickly arrives at 3 and 2, respectively. Adding these all together yields 16.
 +
 
 +
 
 +
Adding all these numbers, <math>20 + 20 + 21 + 16 = \boxed{77} \Rightarrow D</math>

Revision as of 02:15, 3 September 2010

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$

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2010_AMC_12B_Problems/Problem_25&oldid=35730"