2021 Fall AMC 10A Problems/Problem 23

Problem

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?$

$\textbf{(A) }7\qquad\textbf{(B) }8\qquad\textbf{(C) }9\qquad\textbf{(D) }10\qquad\textbf{(E) }11$

Solution

First, We can test values that would make $f(x)=12$ true. For this to happen $x$ must have $6$ divisors, which means its prime factorization is in the form $pq^2$ or $p^5$ , where $p$ and $q$ are prime numbers. Listing out values less than $50$ which have these prime factorizations, we find $12,20,28,44,18,45,50$ for $pq^2$ , and just $32$ for $p^5$ . Here $12$ especially catches our eyes, as this means if one of $f_i(n)=12$ , each of $f_{i+1}(n), f_{i+2}(n), ...$ will all be $12$ . This is because $f_{i+1}(n)=f(f_i(n))$ (as given in the problem statement), so were $f_i(n)=12$ , plugging this in we get $f_{i+1}(n)=f(12)=12$ , and thus the pattern repeats. Hence, as long as for a $i$ , such that $i\leq 50$ and $f_{i}(n)=12$ , $f_{50}(n)=12$ must be true, which also immediately makes all our previously listed numbers, where $f(x)=12$ , possible values of $n$ .

We also know that if $f(x)$ were to be any of these numbers, $x$ would satisfy $f_{50}(n)$ as well. Looking through each of the possibilities aside from $12$ , we see that $f(x)$ could only possibly be equal to $20$ and $18$ , and still have $x$ less than or equal to $50$ . This would mean $x$ must have $10$ , or $9$ divisors, and testing out, we see that $x$ will then be of the form $p^4q$ , or $p^2q^2$ . The only two values less than or equal to $50$ would be $48$ and $36$ respectively. From here there are no more possible values, so tallying our possibilities we count $\boxed{D:10}$ values (Namely $12,20,28,44,18,45,50,32,36,48$ ).

~Ericsz

Page

Toolbox

Search

2021 Fall AMC 10A Problems/Problem 23

Problem

Solution