5th Chinese 1990 Problem A2 What is the longest possible sequence of distinct positive integers with first member 1 and last member 31 a 5 b 1990 c such that each member is divisible by its predecessor? How many such sequences have this length? Solution
: a + b + 3c + 1, (a+b+3c)!/( a! (b+c)! c! c!). Each member of the sequence must have one more prime factor than its predecessor. 31 a 5 b 1990 c = 2 c 5 b+c 31 a 199 c , which has a total of a + b + 3c prime factors. So the longest possible sequence has length a + b + 3c + 1. The number of sequences of maximal length is just (a+b+3c)!/( a! (b+c)! c! c!), since we can choose to add primes in any order. 5th Chinese 1990 © John Scholes jscholes@kalva.demon.co.uk 1 May 2002