# Difference between revisions of "2012 AMC 12B Problems/Problem 24"

## 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.

Numbers $\leq 400$ that are divisible by $2^5$: $12$.

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}$.