36th IMO 1995 shortlist Problem S3 For any integer n > 1, let p(n) be the smallest prime which does not divide n and let q(n) = the product of all primes less than p(n), or 1 if p(n) = 2. Define the sequence a 0 , a 1 , a 2 , ... by a 0 = 1 and a n+1 = a n p(a n )/q(a n ). Find all n such that a n = 1995. Solution
: 142. We calculate the first few terms: 1, 2, 3, 2.3, 5, 2.5, 3.5, 2.3.5, 7, 2.7, 3.7, ... . On that basis we might guess that if p m is the (m+1)th prime and n = b r ... b 0 in binary, then a n = product of primes p i for which b i = 1. q(n) is a product of primes which divide n, so n/q(n) is an integer. Hence a n are all integral. Moreover it is easy to show by induction that a n is square-free. It is true for n = 1. Suppose it is true for n. Since a n+1 is obtained from a n by dropping some prime factors and adding a prime factor not already present, it is true for n+1. Hence for all n. So we can certainly represent a n as a binary number b r ... b 0 , where b m = 1 iff p m divides a m . Now p(a n ) = m, where m is the smallest subscript such that b m = 0 (with the obvious meaning m if a n is represented by m 1s: 1 ... 1). Hence a n+1 is represented by the binary number obtained by adding 1 to that for a n . But a 1 is represented by 1, so a n is represented by the binary expression for n. 1995 = 3.5.7.19, so it is represented by the binary number 10001110 (19 1 17 0 13 0 11 0 7 1 5 1 3 1 2 0 ). Hence the only possible n with a n = 1995 is 10001110 = 128 + 8 + 4 + 2 = 142. 36th IMO shortlist 1995 © John Scholes jscholes@kalva.demon.co.uk 8 Oct 2002