IMO 1995 SL 25

Problem

S3 (POL) For an integer x \geq1, let p(x) be the least prime that does not divide x, and define q(x) to be the product of all primes less than p(x). In particular, p(1) = 2. For x such that p(x) = 2, define q(x) = 1. Consider the sequence x0, x1, x2, . . . defined by x0 = 1 and xn+1 = xnp(xn) q(xn) for n \geq0. Find all n such that xn = 1995.

Solution

By the definition of q(x), it divides x for all integers x > 0, so f(x) = xp(x)/q(x) is a positive integer too. Let {p0, p1, p2, . . . } be all prime num- bers in increasing order. Since it easily follows by induction that all xn’s are square-free, we can assign to each of them a unique code according to which primes divide it: if pm is the largest prime dividing xn, the code corresponding to xn will be . . . 0smsm−1 . . . s0, with si = 1 if pi | xn and si = 0 otherwise. Let us investigate how f acts on these codes. If the code of xn ends with 0, then xn is odd, so the code of f(xn) = xn+1 is obtained from that of xn by replacing s0 = 0 by s0 = 1. Furthermore, if the code of

xn ends with 011 . . .1, then the code of xn+1 ends with 100 . . .0 instead. Thus if we consider the codes as binary numbers, f acts on them as an addition of 1. Hence the code of xn is the binary representation of n and thus xn uniquely determines n. Specifically, if xn = 1995 = 3 \cdot 5 \cdot 7 \cdot 19, then its code is 10001110 and corresponds to n = 142.