Skip to main content

2021 Fall AMC 12A Problem 20

Problem 20 of 25HarderAlgebraNumber Theory

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

Answer choices

Show solution

Solution

Both 88 and 1212 are fixed. For n≤50,n\le50, the first value f1(n)=2d(n)f_1(n)=2d(n) is at most 20.20. Checking the even values through 2020 shows that an orbit reaches 1212 exactly when its first value is 12,18,12,18, or 20.20. Thus we need d(n)=6,9,d(n)=6,9, or 10.10. The numbers at most 5050 with 66 divisors are 12,18,20,28,32,44,45,50;12,18,20,28,32,44,45,50; the only one with 99 divisors is 36,36, and the only one with 1010 divisors is 48.48. These 1010 values all reach the fixed point 12.12. Thus, the correct answer is D.
AoPS wiki

Tagged: factor counting · recursion

More practice