Problem:
Define the function f1 on the positive integers by setting f1(1)=1 and if n=p1e1p2e2⋯pkek is the prime factorization of n>1, then
f1(n)=(p1+1)e1−1(p2+1)e2−1⋯(pk+1)ek−1
For every m≥2, let fm(n)=f1(fm−1(n)). For how many N in the range 1≤N≤400 is the sequence (f1(N),f2(N),f3(N),…) unbounded?
Note: a sequence of positive numbers is unbounded if for every integer B, there is a member of the sequence greater than B.
Answer Choices:
A. 15
B. 16
C. 17
D. 18
E. 19 Solution:
Let SN=(f1(N),f2(N),f3(N),…). If N1 divides N2, then f1(N1) divides f1(N2). Thus SN2 is unbounded if SN1 is unbounded. Call N essential if SN is unbounded and N≤400 is not divisible by any smaller number n such that Sn is unbounded. Assume N=p1e1p2e2⋯pkek is essential. If ej=1 for some j, then f1(N)=f1(pjN). Let n=pjN and note that SN and Sn coincide after the first term and consequently Sn is unbounded. This contradicts the fact that N is essential. Thus ej≥2 for all 1≤j≤k. Moreover, (p1p2⋯pk)2≤p1e1p2e2⋯pkek=N≤400; thus p1p2⋯pk≤400=20. Because 2⋅3⋅5>20 it follows that k≤2.
First analyze the case when n=2a⋅3b. In that case f2(n)=f1(22b−2⋅3a−1)=22a−4⋅32b−3; thus Sn is unbounded if and only if a≥5 or b≥4, and n is essential if and only if n=25 or n=34.
If k=1, then N=pe for some prime p≤19. The cases p=2 or p=3 have been considered before. If p=5, then f1(5a)=2a−1⋅3a−1 and because a≤3, no power of 5 in the given range is essential. If p=7, then f1(7a)=23a−3, and thus N=73 is essential. If p≥11, then p3>400. Because f1(112)=22⋅3, f2(132)=f1(2⋅7)=1,f1(172)=2⋅32, and f2(192)=f1(22⋅5)=3, no powers of 11,13,17, or 19 are essential.
If k=2, then the only possible pairs of primes (p1,p2) are (2,3),(2,5),(2,7), and (3,5). The pair (2,3) was analyzed before and it yields no essential N. If N=2a⋅5b≤400 is essential, then 2≤a≤4 and b=2. Moreover f1(N)=2⋅3a, so a=4 and thus only N=24⋅52 is essential in this case. If (p1,p2)=(2,7) or (3,5) and N=p1e1p2e2≤400 is essential, then N∈{22⋅72,23⋅72,32⋅52}. Because f1(22⋅72)=23⋅3,f1(23⋅72)=23⋅32, and f1(32⋅52)=23⋅3, it follows that there are no essential N in this case.
Therefore the only essential values of N are 25=32,34=81,73=343, and 24⋅52=400. These values have ⌊32400⌋=12,⌊81400⌋=4,⌊343400⌋=1, and ⌊400400⌋=1 multiples, respectively, in the range 1≤N≤400. Because there are no common multiples, the required answer is 12+4+1+1=18.