Problem:
For each positive integer n, let f1​(n) be twice the number of positive integer divisors of n, and for j≥2, let fj​(n)=f1​(fj−1​(n)). For how many values of n≤50 is f50​(n)=12 ?
Answer Choices:
A. 7
B. 8
C. 9
D. 10
E. 11
Solution:
In the table below, p is a prime, and p1​,p2​,… denote distinct primes. Let τ(n) denote the number of positive divisors of n. If n=p1a1​​p2a2​​⋯prar​​, then
τ(n)=(a1​+1)(a2​+1)⋯(ar​+1)
Twelve important observations are found in the third column of the table.
Line ​123456789101112​Factorizationp3p1​p2​p2p1p12​p2​p4p13​p2​p1​p2​p3​p5p12​p22​p14​p2​​ Result ​f1​(n)=8=23,so8isafixedpointoff1​f1​(n)=8andstaysfixedat8,byline1f1​(n)=6=2⋅3,whichgoesto8byline2f1​(n)=4=22,whichgoesto8byline3f1​(1)=2,whichgoesto8byline4f1​(n)=12=22⋅3,so12isafixedpointoff1​f1​(n)=10=2⋅5,whichgoesto8byline2f1​(n)=16=24,whichgoesto8byline7f1​(n)=16=24,whichgoesto8byline7f1​(n)=12=22⋅3,whichstaysat12byline6f1​(n)=18=32⋅2,whichgoesto12byline6f1​(n)=20=22⋅5,whichgoesto12byline6​#21341517122111​​
There are 7 numbers n≤50 whose factorization takes the form p12​p2​, namely 12=22⋅3,18=32⋅2,20=22⋅5, 28=22⋅7,44=22⋅11,45=32⋅5, and 50=52⋅2. There is 1 number n≤50 whose factorization is p5, namely 25=32. There is 1 number n≤50 whose factorization is p12​p22​, namely 22⋅32=36. There is 1 number n≤50 whose factorization is p14​p2​, namely 24⋅3=48. In all, there are 7+1+1+1=(D)10​ numbers n≤50 such that f50​(n)=12.
Note: Pair one divisor d of n with its complementary divisor dn​. Because at least one of d and dn​ is less than or equal to n​, it follows that τ(n)≤2n​ for all n. Hence f1​(n)≤4n​, so f1​(n)<n if n>16. Indeed, after examining 13,14,15, and 16 it emerges that f1​(12)=12, but f1​(n)<n for all n>12.
The estimate for τ(n) used here is convenient because it is easy to prove and it sufficed for the present purpose. With a little more work it can be shown that for every ε>0 there is a constant C(ε) such that τ(n)≤C(ε)nε for all n≥1. Such an argument can be made to yield the best constant C(ε) and an n for which equality is achieved. When ε=21​, the best possible constant is 3​, and equality is achieved when n=12.