2021 AMC Fall 10A Problem 23

Write $d(n)$ for the number of divisors of $n$, so $f_1(n) = 2 \times d(n)$. For example, $12$ has divisors $1, 2, 3, 4, 6, 12$, so $d(12) = 6$ and $f_1(12) = 12$.

Applying $f_1$ fifty times sounds hard, but the numbers get small fast. So first see where the small numbers end up.

1. After one step, the number is small. For $n \le 50$, no number has more than $10$ divisors ($48$ has $10$: $1, 2, 3, 4, 6, 8, 12, 16, 24, 48$). So $f_1(n)$ is an even number from $2$ to $20$.
2. Follow every even number up to $20$.

So $8$ goes to $8$ and $12$ goes to $12$: once there, a number stays forever. Every other number reaches $8$ or $12$ in a few steps: $2 \to 4 \to 6 \to 8$, and $16 \to 10 \to 8$.
3. Which ones end at $12$? Only $12$, $18$ and $20$ (they go straight to $12$). Fifty steps is far more than enough to settle. So $f_{50}(n) = 12$ exactly when $f_1(n)$ is $12$, $18$ or $20$, which means $d(n)$ is $6$, $9$ or $10$.
4. Count divisors with the prime factorization. If $n = p^a q^b$ with different primes $p$, $q$, then $d(n) = (a+1)(b+1)$.
- $d(n) = 6 = 6 \times 1 = 3 \times 2$: $n = p^5$ or $n = p^2 q$. Up to $50$: $32$, and $12, 18, 20, 28, 44, 45, 50$. That is $8$ numbers.
- $d(n) = 9 = 3 \times 3$: $n = p^2 q^2$ (or $p^8$, too big). Only $36$.
- $d(n) = 10 = 5 \times 2$: $n = p^4 q$ (or $p^9$, too big). Only $48 = 2^4 \times 3$.
5. Total. $8 + 1 + 1 = 10$.

The answer is $\boxed{\textbf{(D)}\ 10}$.

When a function is applied over and over, look at where the values go after one step. Here every starting number lands among ten small even numbers, and a short table shows each one ends at $8$ or $12$. Then work backwards: which first steps lead to $12$? That leaves a standard count of numbers with a given number of divisors.

Write $d(n)$ for the number of divisors, so $f_1(n) = 2d(n)$.

Where do iterates go? For $n \le 50$, $d(n) \le 10$ (the maximum is $d(48) = 10$), so $f_1(n)$ is an even number at most $20$. Now track every even number up to $20$:
$$2 \to 4 \to 6 \to 8 \to 8, \qquad 10 \to 8, \qquad 14 \to 8, \qquad 16 \to 10 \to 8,$$
$$12 \to 12, \qquad 18 \to 12, \qquad 20 \to 12.$$
So $8$ and $12$ are the only fixed points, and after one step every $n \le 50$ is at some even number $\le 20$, which then falls into $8$ or $12$ within a few steps. Hence $f_{50}(n) = 12$ exactly when $f_1(n) \in \{12, 18, 20\}$, i.e. when $d(n) \in \{6, 9, 10\}$.

Count. Using $d(p^a q^b) = (a+1)(b+1)$:

• $d(n) = 6$: $n = p^5$ or $p^2 q$. Up to $50$: $32$; $12, 18, 20, 28, 44, 45, 50$. That is $8$ numbers.
• $d(n) = 9$: $n = p^8$ or $p^2 q^2$. Only $36$.
• $d(n) = 10$: $n = p^9$ or $p^4 q$. Only $48$.

Total $8 + 1 + 1 = 10$.

The answer is $\boxed{\textbf{(D)}\ 10}$.