Problem:
Define the function f1​ on the positive integers by setting f1​(1)=1 and if n=p1e1​​p2e2​​⋯pkek​​ is the prime factorization of n>1, then
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=p1e1​​p2e2​​⋯pkek​​ is essential. If ej​=1 for some j, then f1​(N)=f1​(pj​N​). Let n=pj​N​ 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, (p1​p2​⋯pk​)2≤p1e1​​p2e2​​⋯pkek​​=N≤400; thus p1​p2​⋯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=p1e1​​p2e2​​≤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​.