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 a0, a1, a2, ... by a0 = 1 and an+1 = anp(an)/q(an). Find all n such that an = 1995.
Solution
Answer: 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 pm is the (m+1)th prime and n = br ... b0 in binary, then an = product of primes pi for which bi = 1.
q(n) is a product of primes which divide n, so n/q(n) is an integer. Hence an are all integral. Moreover it is easy to show by induction that an is square-free. It is true for n = 1. Suppose it is true for n. Since an+1 is obtained from an 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 an as a binary number br ... b0, where bm = 1 iff pm divides am. Now p(an) = m, where m is the smallest subscript such that bm = 0 (with the obvious meaning m if an is represented by m 1s: 1 ... 1). Hence an+1 is represented by the binary number obtained by adding 1 to that for an. But a1 is represented by 1, so an is represented by the binary expression for n.
1995 = 3.5.7.19, so it is represented by the binary number 10001110 (19117013011071513120). Hence the only possible n with an = 1995 is 10001110 = 128 + 8 + 4 + 2 = 142.
© John Scholes
jscholes@kalva.demon.co.uk
8 Oct 2002