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+1βX(xnβ)=xnβp(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=dmβdmβ1ββ¦d1βd0ββ=βi=0mβdiβ2i(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β)x0βp(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=1mβdiβ2i 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=1mβdiβ2i, it follows that xn+1β=Ο0ββi=1mβΟiβdi 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=dmβdmβ1ββ¦dj+1β011β¦11β=βi=0jβ1β2i+βi=j+1mβdiβ2i. 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=dmβdmβ1ββ¦dj+1β100β¦00β= 2j+βi=j+1mβdiβ2i, 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=0mβ2i. 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