For each positive integer n, let d(n) be the largest odd divisor of n and define f(n) to be n/2 + n/d(n) for n even and 2(n+1)/2 for n odd. Define the sequence a1, a2, a3, ... by a1 = 1, an+1 = f(an). Show that 1992 occurs in the sequence and find the first time it occurs. Does it occur more than once?
Answer
a8250 = 1992. No.
Solution
The first few terms are 1, 2, 3, 4, 6, 5, 8, 12, 10, 7, 16, 24, 20, 14, 9, ... . Take fm(n) to mean that f is composed with itself m times. We claim that fm(2n) = (2m+1)2n-m for m ≤ n. Induction on m. For m = 1 we have f(2n) = 2n/2 + 2n/1 = 3·2n-1, as required. So if it is true for m, then fm+1(2n) = f((2m+1)2n-m) = (2m+1)2n-m-1 + 2n-m = (2m+3)2n-(m+1), as required. Hence it is true for all m ≤ n. Also, we have f(2m+1) = 2m+1. So fm+2(2m+1) = 2m+3, and all the intervening terms are even. In fact we can write the terms as a triangle:
1 1·21 3·1 1·22 3·21 5·1 1·23 3·22 5·21 7·1 1·24 3·23 5·22 7·21 9·1 ...It is clear that each positive integer occurs in the sequence exactly once. We have 1992 = 8·249. We have a1 = 1, a1+2 = 3, a1+2+3 = 5, ... a1+2+...+k = ak(k+1)/2 = 2k-1, so 249 = a7875. That row has 125 terms. Then 2·249 = a7875+125, 4·249 = a7875+125+125, 8·249 = a7875+125+125+125 = a8250.
© John Scholes
jscholes@kalva.demon.co.uk
25 Nov 2003
Last updated/corrected 25 Nov 2003