Hofstadter-Conway $10,000 Sequence

The Integer Sequence defined by the Recurrence Relation

$$a(n)=a(a(n-1))+a(n-a(n-1))$$

with $a(1)=a(2)=1$. The first few values are 1, 1, 2, 2, 3, 4, 4, 4, 5, 6, ... (Sloane's A004001). Plotting $a(n)/n$ against $n$ gives the Batrachion plotted below. Conway (1988) showed that $\lim_{n\to\infty} a(n)/n=1/2$ and offered a prize of $10,000 to the discoverer of a value of $n$ for which $\vert a(i)/i-1/2\vert<1/20$ for $i>n$. The prize was subsequently claimed by Mallows, after adjustment to Conway's ``intended'' prize of $1,000 (Schroeder 1991), who found $n=1489$.

$a(n)/n$ takes a value of 1/2 for $n$ of the form $2^k$ with $k=1$, 2, .... Pickover (1996) gives a table of analogous values of $n$ corresponding to different values of $\vert a(n)/n-1/2\vert<e$.

See also Blancmange Function, Hofstadter's Q-Sequence, Mallow's Sequence

References

Conolly, B. W. ``Meta-Fibonacci Sequences.'' In Fibonacci and Lucas Numbers, and the Golden Section (Ed. S. Vajda). New York: Halstead Press, pp. 127-138, 1989.

Conway, J. ``Some Crazy Sequences.'' Lecture at AT&T Bell Labs, July 15, 1988.

Guy, R. K. ``Three Sequences of Hofstadter.'' §E31 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 231-232, 1994.

Kubo, T. and Vakil, R. ``On Conway's Recursive Sequence.'' Disc. Math. 152, 225-252, 1996.

Mallows, C. ``Conway's Challenging Sequence.'' Amer. Math. Monthly 98, 5-20, 1991.

Pickover, C. A. ``The Drums of Ulupu.'' In Mazes for the Mind: Computers and the Unexpected. New York: St. Martin's Press, 1993.

Pickover, C. A. ``The Crying of Fractal Batrachion 1,489.'' Ch. 25 in Keys to Infinity. New York: W. H. Freeman, pp. 183-191, 1995.

Schroeder, M. ``John Horton Conway's `Death Bet.''' Fractals, Chaos, Power Laws. New York: W. H. Freeman, pp. 57-59, 1991.

Sloane, N. J. A. Sequence A004001/M0276 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.