Skip to main content

2021 Fall AMC 10A Problem 23

Problem 23 of 25HarderAlgebraNumber TheoryProblem-Solving Techniques

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

The value 1212 is fixed by the function, since 1212 has 66 positive divisors and therefore f1(12)=12.f_1(12)=12. First find all n≤50n\le50 with f1(n)=12,f_1(n)=12, meaning nn has 66 divisors. These are 12,18,20,28,32,44,45,50.12,18,20,28,32,44,45,50. Now check whether f1(n)f_1(n) can be one of these values before reaching 12.12. Since f1(n)f_1(n) is twice a divisor count, the only useful possibilities in that list are 1818 and 20,20, meaning nn has 99 or 1010 divisors. For n≤50,n\le50, the additional possibilities are 36,36, which has 99 divisors, and 48,48, which has 1010 divisors. Therefore there are 8+2=108+2=10 values of n.n. Thus, D is the correct answer.
AoPS wiki

Tagged: factor counting · recursion · work backwards

More practice