S.KRAUSE

The Conway Series

The following text was taken from: http://www.cs.ruu.nl/wais/html/na-dir/puzzles/archive/arithmetic/part1.html Some text has been deleted, so see the original document for more information.

PROBLEM

Describe the sequence:

a(1)=a(2)=1, a(n) = a(a(n-1)) + a(n-a(n-1)) for n>2.

SOLUTION

This sequence and its remarkable properties were discovered, apparently independently, by Douglas Hofstadter (circa 1975), John Conway (in the early 1980's), B.W. Connoly, and others. Since Conway discovered many of the deeper properties, and is the one responsible for popularizing the sequence, it seems appropriate to name the sequence after him.

Some properties of a(n):

• a(n+1) - a(n) = 0 or 1
• a(2^n) = 2^(n-1)
• n/2 <= a(n) <= n
• A(n)= 2a(n) - n has zeros at the powers of 2 and positive "humps" in between
• A(2^n + t) = A(2^(n+1) - t) for t between 0 and 2^n, i.e. the humps are symmetric
• a(2n) <= 2a(n)
• a(n)/n --> 1/2 as n --> infinity
• a(n) and A(n) are self-similar, in the sense that their values on the (N+1)'st hump can be obtained by a "magnification" process applied to the values on the N'th hump. They are *not* chaotic sequences, since their asymptotics and combinatorial structure are very regular and rigid.

In a lecture at Bell Labs in 1988, Conway asked for the rate at which a(n)/n converges to 1/2. In particular, he asked for N(epsilon), the last value of n such that |a(n)/n - 1/2| exceeds epsilon, in the case epsilon=1/20. This problem was solved by Colin Mallows of Bell Labs: he found that N(1/20)=1489 and N(1/40)=6083008742. These values are reported in his article in the American Mathematical Monthly, January 1991, p. 5.

Conway's sequence has a deep combinatorial structure, and is intimately connected with all of the following: variants of Pascal's triangle, the Gaussian distribution, combinatorial operations on finite sets, coin-pushing games, and Fibonacci and Catalan numbers.