TOPICS
Search

Hofstadter-Conway $10,000 Sequence


The recursive sequence defined by the recurrence relation

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

with a(1)=a(2)=1. The first few values are 1, 1, 2, 2, 3, 4, 4, 4, 5, 6, ... (OEIS A004001; Wolfram 2002, pp. 129-130, sequence (c)). Conway (1988) showed that lim_(n->infty)a(n)/n=1/2 and offered a prize of $10000 to the discoverer of a value of n for which |a(i)/i-1/2|<1/20 for i>n. The prize was subsequently claimed by Mallows, after adjustment to Conway's "intended" prize of $1000 (Schroeder 1991), who found n=1489.

HofstadterConwaySequence

The plots above show a(n)/n (left plot) and a(n)-n/2 (right plot). Amazingly, a(n)-n/2 reveals itself to consist of a series of increasingly larger versions of the batrachion Blancmange function.

a(n)/n takes a value of 1/2 for n of the form 2^k with k=1, 2, .... More generally,

 a(2^k)=2^(k-1)
(2)

and

 a(2n)<=2a(n).
(3)

Pickover (1995) gives a table of analogous values of n corresponding to different values of |a(n)/n-1/2|<e.

HofstadterConway2

A related chaotic sequence is given by the recurrence equation

 b(n)=b(b(n-1))+b(n-b(n-2)-1)
(4)

with b(1)=b(2)=1, which gives the sequence 1, 1, 2, 2, 2, 3, 4, 4, 4, 4, 5, 6, 7, 8, 8, 8, 8, 8, 8, ... (OEIS A055748; Pinn 2000; Wolfram 2002, pp. 129-130, sequence (g)).


See also

Blancmange Function, Hofstadter's Q-Sequence, Mallows' Sequence

Explore with Wolfram|Alpha

References

Bloom, D. M. "Newman-Conway Sequence." Solution to Problem 1459. Math. Mag. 68, 400-401, 1995.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. L. "Conway's Challenge 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 1489." Ch. 25 in Keys to Infinity. New York: W. H. Freeman, pp. 183-191, 1995.Pickover, C. A. "The Crying of Fractal Batrachion 1489." Comput. & Graphics 19, 611-615, 1995. Reprinted in Chaos and Fractals, A Computer Graphical Journey: Ten Year Compilation of Advanced Research (Ed. C. A. Pickover). Amsterdam, Netherlands: Elsevier, pp. 127-131, 1998.Pinn, K. "A Chaotic Cousin of Conway's Recursive Sequence." Exp. Math. 9, 55-66, 2000.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. Sequences A004001/M0276 and A055748 in "The On-Line Encyclopedia of Integer Sequences."Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, pp. 129-130, 2002.

Referenced on Wolfram|Alpha

Hofstadter-Conway $10,000 Sequence

Cite this as:

Weisstein, Eric W. "Hofstadter-Conway $10,000 Sequence." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Hofstadter-Conway10000-DollarSequence.html

Subject classifications