Question

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 \gt 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), \ldots)$ unbounded? Note: a sequence of positive numbers is unbounded if for every integer $B,$ there is a member of the sequence greater than $B.$

$15$

$16$

$17$

$18$

$19$

Solution:

If $N_1\mid N_2$ then $f_1(N_1)\mid f_1(N_2),$ so if $S_{N_1}$ is unbounded so is $S_{N_2}.$ Call $N$ essential if it is unbounded but no proper divisor is. An essential $N$ must have all exponents at least $2,$ and $(p_1\cdots p_k)^2\le400$ forces at most two primes.

Checking prime powers and prime pairs, the essential values are $2^5=32,$ $3^4=81,$ $7^3=343,$ and $2^4\cdot5^2=400.$

Their multiples up to $400$ number $\lfloor400/32\rfloor=12,$ $\lfloor400/81\rfloor=4,$ $\lfloor400/343\rfloor=1,$ and $\lfloor400/400\rfloor=1,$ with no overlaps, for a total of $12+4+1+1=18.$

Thus, the correct answer is D.

2012 AMC 12B Problem 24

Solution:

Problem 24 in Other Years