Hofstadter's Q-Sequence

$\begin{figure}\begin{center}\BoxedEPSF{HofstadterQ.epsf}\end{center}\end{figure}$

$\begin{displaymath} Q(n)=Q(n-Q(n-1))+Q(n-Q(n-2)), \end{displaymath}$

with

. The first few values are 1, 1, 2, 3, 3, 4, 5, 5, 6, 6, ... (Sloane's A005185; illustrated above). These numbers are sometimes called Q-Number.

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.

Guy, R. ``Some Suspiciously Simple Sequences.'' Amer. Math. Monthly 93, 186-191, 1986.

Hofstadter, D. R. Gödel, Escher Bach: An Eternal Golden Braid. New York: Vintage Books, pp. 137-138, 1980.

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.

Sloane, N. J. A. Sequence A005185/M0438 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.