2021 AMC Fall 10A Problem 23

P21-25~9 minPrint

Divisibility & Factors Sequences & Series Organized listing / direct enumeration Compute small cases, spot the pattern, generalize Start from the end state / desired conclusion and reverse

For each positive integer $n$ , let $f_1(n)$ be twice the number of positive integer divisors of $n$ , and for $j \ge 2$ , let $f_j(n) = f_1(f_{j-1}(n))$ . For how many values of $n \le 50$ is $f_{50}(n) = 12?$

Show solution without answering

Key insight

For n up to 50, f1(n) is an even number at most 20. Only 12, 18 and 20 end at 12, so count n with 6, 9 or 10 divisors.

Solution

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.

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$ .
Follow every even number up to $20$ .

$m$	2	4	6	8	10	12	14	16	18	20
$d(m)$	2	3	4	4	4	6	4	5	6	6
$f_1(m)$	4	6	8	8	8	12	8	10	12	12

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

Why this works

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.

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

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

Review in the AoPS books

Introduction to Number Theory, Chapter 1: Integers: The Basics (§1.4, §1.5)
Introduction to Algebra, Chapter 21: Sequences & Series (§21.1, §21.2, §21.3, §21.4)
Prealgebra, Chapter 15: Problem-Solving Strategies (§15.1)
Introduction to Number Theory, Chapter 5: Divisor Problems (§5.2, §5.3)