A chaotic cousin of Conway’s recursive sequence. (English) Zbl 0959.05007

Summary: I introduce the recurrence \(D(n)= D(D(n-1))+ D(n- 1- D(n- 2))\), \(D(1)= D(2)= 1\), and study it by means of computer experiments. The definition of \(D(n)\) has some similarity to that of Conway’s sequence defined by \(a(n)= a(a(n- 1))+ a(n- a(n- 1))\), \(a(1)= a(2)= 1\). However, unlike the completely regular and predictable behaviour of \(a(n)\), the \(D\)-numbers exhibit chaotic patterns. In its statistical properties, the \(D\)-sequence shows striking similarities with Hofstadter’s \(Q(n)\)-sequence, given by \(Q(n)= Q(n- Q(n- 1))+ Q(n- Q(n- 2))\), \(Q(1)= Q(2)= 1\); see Douglas R. Hofstadter [Gödel, Escher, Bach: an eternal golden braid (1979; reprint 1981; Zbl 0457.03001)]. Compared to the Hofstadter sequence, \(D\) shows higher structural order. It is organized in well-defined “generations”, separated by smooth and predictable regions. The article is complemented by a study of two further recurrence relations with definitions similar to those of the \(Q\)-numbers. There is some evidence that the different sequences studied share a universality class.


05A15 Exact enumeration problems, generating functions
11B83 Special sequences and polynomials
11B37 Recurrences


Zbl 0457.03001
Full Text: DOI arXiv EuDML


[1] Barbeau E., Electron. J. Combin. 3 (1) pp 9– (1996)
[2] Barbeau E. J., Electron. J. Combin. 4 (1) pp 11– (1997)
[3] Bouchaud J.-P., Phys. Rep. 195 (4) pp 127– (1990)
[4] Conolly B. W., Fibonacci & Lucas numbers, and the golden section: theory and applications pp 127– (1989)
[5] Guy, R. K. 1981.Unsolved problems in number theory186–190. New York: Springer. [Guy 1981], Problem Books in Math., See also his column in Amer. Math. Monthly 93 (1986)
[6] Hofstadter D. R., Gödel, Escher, Bach: an eternal golden braid (1979)
[7] Hofstadter, D. R. September 2 1988. September 2, [Hofstadter 1988], Letters to C. Mallows and J. H. Conway
[8] Kubo T., Discrete Math. 152 (1) pp 225– (1996) · Zbl 0852.05010
[9] Mallows C. L., Amer. Math. Monthly 98 (1) pp 5– (1991) · Zbl 0738.11014
[10] Pinn K., Complexity 4 (3) pp 41– (1999)
[11] Tanny S. M., Discrete Math. 105 (1) pp 227– (1992) · Zbl 0766.11008
[12] Yao, A. K. 1997. [Yao 1997], Private communication via D. R. Hofstadter
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.