Problem:
For any integer k≥1, let p(k) be the smallest prime which does not divide k. Define the integer function X(k) to be the product of all primes less than p(k) if p(k)>2, and X(k)=1 if p(k)=2. Let {xn} be the sequence defined by x0=1, and xn+1X(xn)=xnp(xn) for n≥0. Find the smallest positive integer, t such that xt=2090.
Solution:
Number the primes as follows: ρ0=2,ρ1=3,ρ2=5,…. It turns out that each xn can be expressed in terms of the digits of the binary representation of n. That is
∗ If the binary representation of n=dmdm−1…d1d0=∑i=0mdi2i(di∈{0,1}), then xn=∏i=0mρidi.
The claim can be proved by mathematical induction on n as follows.
For n=1(∗) holds true, because x1=X(x0)x0p(x0)=X(1)p(1)=2. Proceeding by induction, assume that (∗) holds true for some integer n≥1. If n is an even integer, then d0=0, and so n=∑i=1mdi2i and xn=∏i=1mρidi. Therefore p(xn)=2,X(xn)=1, and by the definition of {xn},xn+1=2xn. Because n+1=20+∑i=1mdi2i, it follows that xn+1=ρ0∏i=1mρidi proving that (∗) holds true for n+1 if n is even.
Assume now that n is odd, so d0=1. Consider two cases: n=2m+1−1 or n=2m+1−1 for some positive integer m. In the first case the binary representation of n contains at least one digit 0. Let j be the smallest number for which dj=0, that is n=dmdm−1…dj+1011…11=∑i=0j−12i+∑i=j+1mdi2i. By the induction hypothesis xn=∏i=0j−1ρi⋅∏i=j+1mρidi. Thus p(xn)=ρj, and X(xn)=∏i=0j−1ρi. It follows that n+1=dmdm−1…dj+1100…00= 2j+∑i=j+1mdi2i, and the recurrence implies xn+1=X(xn)xnρj=ρj∏i=j+1mρidi, proving (∗) in this case.
Consider now the case n=2m+1−1, so the binary representation of n contains only ones, so n=11…11=∑i=0m2i. In this case p(xn)=ρm+1, and X(xn)= ∏i=0mρi=xn. Therefore xn+1=X(xn)xnρm+1=ρm+1, and n+1=2m+1, proving (∗) in this case and completing the proof by induction.
Note that as a consequence of this claim each xn is a unique square-free integer. Because 2090=2⋅5⋅11⋅19=ρ0⋅ρ2⋅ρ4⋅ρ7, the requested value of t= 20+22+24+27=149.
The problems on this page are the property of the MAA's American Mathematics Competitions