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.