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)
(→‎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.
+
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.
−
 
 
−
Numbers <math>\leq 400</math> that are divisible by <math>2^5</math>: <math>12</math>.
 
  
 
Any first power of prime will not contribute, so at least we look for square of primes. We test primes that are less than <math>\sqrt{400}=20</math>:
 
Any first power of prime will not contribute, so at least we look for square of primes. We test primes that are less than <math>\sqrt{400}=20</math>:

Revision as of 05:18, 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$. Now let's look at the other cases.

Any first power of prime will not contribute, so at least we look for square of primes. 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$ is odd, but $3^3 \cdot 5^2 >400$ already.

$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^3$ could also work if $Q$ is odd, but $7^2 \cdot 3^3 > 400$ already.

$f_1(11^2 \cdot 3) = 2^4 \cdot 3$ does not work.

When prime $p\geq 13$, any odd multiple $p^2$ other than itself is greater than $400$, and that $f_1(p^2)=p+1$ could be a multiple of $32$ only if $p\geq 31$, which is already beyond what we need to test.

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

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