TOPICS
Search

Hofstadter's Q-Sequence


HofstadterQ

The recursive sequence generated by the recurrence equation

 Q(n)=Q(n-Q(n-1))+Q(n-Q(n-2)),

with Q(1)=Q(2)=1. The first few values are 1, 1, 2, 3, 3, 4, 5, 5, 6, 6, ... (OEIS A005185; Wolfram 2002, pp. 129-130, sequence (e); Wolfram 2022). These numbers are /sometimes called Q-numbers. The Hofstadter Q-sequence can be implemented in the Wolfram Language as

Hofstadter[1] = Hofstadter[2] = 1;
Hofstadter[n_Integer?Positive] := Hofstadter[n] = Block[
   {$RecursionLimit = Infinity},
   Hofstadter[n - Hofstadter[n - 1]] +
    Hofstadter[n - Hofstadter[n - 2]]
   ]

There are currently no rigorous analyses or detailed predictions of the rather erratic behavior of Q(n) (Guy 1994). It has, however, been demonstrated that the chaotic behavior of the Q-numbers shows some signs of order, namely that they exhibit approximate period doubling, self-similarity and scaling (Pinn 1999, 2000). These properties are shared with the related sequence

 D(n)=D(D(n-1))+D(n-1-D(n-2))

with D(1)=D(2)=1, which exhibits exact period doubling (Pinn 1999, 2000). The chaotic regions of D(n) are separated by predictable smooth behavior.


See also

Hofstadter-Conway $10,000 Sequence, Mallows' Sequence, Period Doubling

Explore with Wolfram|Alpha

References

Conolly, B. W. "Fibonacci and Meta-Fibonacci Sequences." In Fibonacci and Lucas Numbers, and the Golden Section (Ed. S. Vajda). New York: Halstead Press, pp. 127-138, 1989.Dawson, R.; Gabor, G.; Nowakowski, R.; and Weins, D. "Random Fibonacci-Type Sequences." Fib. Quart. 23, 169-176, 1985.Guy, R. "Some Suspiciously Simple Sequences." Amer. Math. Monthly 93, 186-191, 1986.Guy, R. K. "Three Sequences of Hofstadter." §E31 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 231-232, 1994.Hofstadter, D. R. Gödel, Escher Bach: An Eternal Golden Braid. New York: Vintage Books, pp. 137-138, 1980.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 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.Pickover, C. A. "The Crying of Fractal Batrachion 1489." Ch. 25 in Keys to Infinity. New York: W. H. Freeman, pp. 183-191, 1995.Pinn, K. "Order and Chaos is Hofstadter's Q(n) Sequence." Complexity 4, 41-46, 1999.Pinn, K. "A Chaotic Cousin of Conway's Recursive Sequence." Exper. Math. 9, 55-66, 2000.Sloane, N. J. A. Sequence A005185/M0438 in "The On-Line Encyclopedia of Integer Sequences."Tanny, S. M. "A Well-Behaved Cousin of the Hofstadter Sequence." Disc. Math. 105, 227-239, 1992.Wolfram, S. "Recursive Sequences." A New Kind of Science. Champaign, IL: Wolfram Media, pp. 128-131, 2002.Wolfram, S. "What We've Learned from NKS Chapter 4: Systems Based on Numbers." Around minute 34:00. 2022. https://www.youtube.com/watch?v=2BbO5mr094A.

Referenced on Wolfram|Alpha

Hofstadter's Q-Sequence

Cite this as:

Weisstein, Eric W. "Hofstadter's Q-Sequence." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/HofstadtersQ-Sequence.html

Subject classifications