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 "2012 AMC 12B Problems/Problem 24"

(→‎Solution: missed an important case)
(→‎Solution)
Line 11: Line 11:
 
== Solution ==
 
== Solution ==
  
−
First of all, notice that for any odd prime <math>p</math>, the largest prime that divides <math>p+1</math> is no larger than <math>\frac{p+1}{2}</math>, therefore eventually the factorization of <math>f_k(N)</math> does not contain any prime larger than <math>3</math>. Also, note that <math>f_2(2^m) = f_1(3^{m-1})=2^{2m-4}</math>, when <math>m=4</math> it stays the same but when <math>m\geq 5</math> it grows indefinitely. Therefore any number <math>N</math> that is divisible by <math>2^5</math> or any number <math>N</math> such that <math>f_k(N)</math> is divisible by <math>2^5</math> makes the sequence <math>(f_1(N),f_2(N),f_3(N),\dots )</math> unbounded. There are <math>12</math> multiples of <math>2^5</math> within <math>400</math>. Now let's look at the other cases.
+
First of all, notice that for any odd prime <math>p</math>, the largest prime that divides <math>p+1</math> is no larger than <math>\frac{p+1}{2}</math>, therefore eventually the factorization of <math>f_k(N)</math> does not contain any prime larger than <math>3</math>. Also, note that <math>f_2(2^m) = f_1(3^{m-1})=2^{2m-4}</math>, when <math>m=4</math> it stays the same but when <math>m\geq 5</math> it grows indefinitely. Therefore any number <math>N</math> that is divisible by <math>2^5</math> or any number <math>N</math> such that <math>f_k(N)</math> is divisible by <math>2^5</math> makes the sequence <math>(f_1(N),f_2(N),f_3(N),\dots )</math> unbounded. There are <math>12</math> multiples of <math>2^5</math> within <math>400</math>. <math>2^4 5^2=400</math> also works: <math>f_2(2^4 5^2) = f_1(3^4 \cdot 2) = 2^6</math>.
  
−
Any first power of prime in a prime factorization will not contribute the unboundedness because <math>f_1(p^1)=(p+1)^0=1</math>. At least a square of prime is to contribute. So we test primes that are less than <math>\sqrt{400}=20</math>:
+
Now let's look at the other cases. Any first power of prime in a prime factorization will not contribute the unboundedness because <math>f_1(p^1)=(p+1)^0=1</math>. At least a square of prime is to contribute. So we test primes that are less than <math>\sqrt{400}=20</math>:
  
 
<math>f_1(3^4)=4^3=2^6</math> works, therefore any number <math>\leq 400</math> that are divisible by <math>3^4</math> works: there are <math>4</math> of them.
 
<math>f_1(3^4)=4^3=2^6</math> works, therefore any number <math>\leq 400</math> that are divisible by <math>3^4</math> works: there are <math>4</math> of them.
Line 25: Line 25:
 
<math>7^2 \cdot Q^2</math> could also work if <math>4~|~f_1(Q^2)</math>, but <math>7^2 \cdot 3^2 > 400</math> already.
 
<math>7^2 \cdot Q^2</math> could also work if <math>4~|~f_1(Q^2)</math>, but <math>7^2 \cdot 3^2 > 400</math> already.
  
−
For number that are only divisible by <math>p=11, 13, 19</math>, they don't work because none of these primes are such that <math>p+1</math> could be a multiple of <math>2^5</math> nor a multiple of <math>3^4</math>.
+
For number that are only divisible by <math>p=11, 13, 17, 19</math>, they don't work because none of these primes are such that <math>p+1</math> could be a multiple of <math>2^5</math> nor a multiple of <math>3^4</math>.
  
−
<math>p=17</math> works because <math>f_1(17^2) = 18=3^4 \cdot 2</math>.
+
In conclusion, there are <math>12+1+4+1=18</math> number of <math>N</math>'s ... <math>\framebox{D}</math>.
−
 
 
−
In conclusion, there are <math>12+4+1+1=18</math> number of <math>N</math>'s ... <math>\framebox{D}</math>.
 

Revision as of 04:55, 6 December 2012

Problem 24

Define the function $f_1$ on the positive integers by setting $f_1(1)=1$ and if $n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$ is the prime factorization of $n>1$, then \[f_1(n)=(p_1+1)^{e_1-1}(p_2+1)^{e_2-1}\cdots (p_k+1)^{e_k-1}.\] For every $m\ge 2$, let $f_m(n)=f_1(f_{m-1}(n))$. For how many $N$ in the range $1\le N\le 400$ is the sequence $(f_1(N),f_2(N),f_3(N),\dots )$ unbounded?

Note: A sequence of positive numbers is unbounded if for every integer $B$, there is a member of the sequence greater than $B$.

$\textbf{(A)}\ 15\qquad\textbf{(B)}\ 16\qquad\textbf{(C)}\ 17\qquad\textbf{(D)}\ 18\qquad\textbf{(E)}\ 19$


Solution

First of all, notice that for any odd prime $p$, the largest prime that divides $p+1$ is no larger than $\frac{p+1}{2}$, therefore eventually the factorization of $f_k(N)$ does not contain any prime larger than $3$. Also, note that $f_2(2^m) = f_1(3^{m-1})=2^{2m-4}$, when $m=4$ it stays the same but when $m\geq 5$ it grows indefinitely. Therefore any number $N$ that is divisible by $2^5$ or any number $N$ such that $f_k(N)$ is divisible by $2^5$ makes the sequence $(f_1(N),f_2(N),f_3(N),\dots )$ unbounded. There are $12$ multiples of $2^5$ within $400$. $2^4 5^2=400$ also works: $f_2(2^4 5^2) = f_1(3^4 \cdot 2) = 2^6$.

Now let's look at the other cases. Any first power of prime in a prime factorization will not contribute the unboundedness because $f_1(p^1)=(p+1)^0=1$. At least a square of prime is to contribute. So we test primes that are less than $\sqrt{400}=20$:

$f_1(3^4)=4^3=2^6$ works, therefore any number $\leq 400$ that are divisible by $3^4$ works: there are $4$ of them.

$3^3 \cdot Q^2$ could also work if $Q^2$ satisfies $2~|~f_1(Q^2)$, but $3^3 \cdot 5^2 > 400$.

$f_1(5^3)=6^2 = 2^2 3^2$ does not work.

$f_1(7^3)=8^2=2^6$ works. There are no other multiples of $7^3$ within $400$.

$7^2 \cdot Q^2$ could also work if $4~|~f_1(Q^2)$, but $7^2 \cdot 3^2 > 400$ already.

For number that are only divisible by $p=11, 13, 17, 19$, they don't work because none of these primes are such that $p+1$ could be a multiple of $2^5$ nor a multiple of $3^4$.

In conclusion, there are $12+1+4+1=18$ number of $N$'s ... $\framebox{D}$.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2012_AMC_12B_Problems/Problem_24&oldid=49805"