cp's OEIS Frontend

A004001 Hofstadter-Conway $10000 sequence: a(n) = a(a(n-1)) + a(n-a(n-1)) with a(1) = a(2) = 1.

%I A004001 M0276 #186 Feb 16 2025 08:32:27
%S A004001 1,1,2,2,3,4,4,4,5,6,7,7,8,8,8,8,9,10,11,12,12,13,14,14,15,15,15,16,
%T A004001 16,16,16,16,17,18,19,20,21,21,22,23,24,24,25,26,26,27,27,27,28,29,29,
%U A004001 30,30,30,31,31,31,31,32,32,32,32,32,32,33,34,35,36,37,38,38,39,40,41,42
%N A004001 Hofstadter-Conway $10000 sequence: a(n) = a(a(n-1)) + a(n-a(n-1)) with a(1) = a(2) = 1.
%C A004001 On Jul 15 1988 during a colloquium talk at Bell Labs, John Conway stated that he could prove that a(n)/n -> 1/2 as n approached infinity, but that the proof was extremely difficult. He therefore offered $100 to someone who could find an n_0 such that for all n >= n_0, we have |a(n)/n - 1/2| < 0.05, and he offered $10,000 for the least such n_0. I took notes (a scan of my notebook pages appears below), plus the talk - like all Bell Labs Colloquia at that time - was recorded on video. John said afterwards that he meant to say $1000, but in fact he said $10,000. I was in the front row. The prize was claimed by Colin Mallows, who agreed not to cash the check. - _N. J. A. Sloane_, Oct 21 2015
%C A004001 a(n) - a(n-1) = 0 or 1 (see the D. Newman reference). - _Emeric Deutsch_, Jun 06 2005
%C A004001 a(A188163(n)) = n and a(m) < n for m < A188163(n). - _Reinhard Zumkeller_, Jun 03 2011
%C A004001 From _Daniel Forgues_, Oct 04 2019: (Start)
%C A004001 Conjectures:
%C A004001   a(n) = n/2 iff n = 2^k, k >= 1.
%C A004001   a(n) = 2^(k-1): k times, for n = 2^k - (k-1) to 2^k, k >= 1. (End)
%D A004001 J. Arkin, D. C. Arney, L. S. Dewald and W. E. Ebel, Jr., Families of recursive sequences, J. Rec. Math., 22 (No. 22, 1990), 85-94.
%D A004001 B. W. Conolly, Meta-Fibonacci sequences, in S. Vajda, editor, "Fibonacci and Lucas Numbers and the Golden Section", Halstead Press, NY, 1989, pp. 127-138.
%D A004001 R. K. Guy, Unsolved Problems Number Theory, Sect. E31.
%D A004001 D. R. Hofstadter, personal communication.
%D A004001 C. A. Pickover, Wonders of Numbers, "Cards, Frogs and Fractal sequences", Chapter 96, pp. 217-221, Oxford Univ. Press, NY, 2000.
%D A004001 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D A004001 S. Vajda, Fibonacci and Lucas Numbers and the Golden Section, Wiley, 1989, see p. 129.
%D A004001 S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 129.
%H A004001 T. D. Noe, <a href="/A004001/b004001.txt">Table of n, a(n) for n = 1..10000</a>
%H A004001 Altug Alkan, <a href="https://doi.org//10.1155/2018/8517125">On a Generalization of Hofstadter's Q-Sequence: A Family of Chaotic Generational Structures</a>, Complexity (2018) Article ID 8517125.
%H A004001 Altug Alkan and O. Ozgur Aybar, <a href="/A004001/a004001_5.pdf">On Families of Solutions for Meta-Fibonacci Recursions Related to Hofstadter-Conway $10000 Sequence</a>, Slides of talk at presented in 5th International Interdisciplinary Chaos Symposium on Chaos and Complex Systems, May 9-12, 2019.
%H A004001 Altug Alkan, Nathan Fox, and Orhan Ozgur Aybar, <a href="https://doi.org/10.1155/2017/2614163">On Hofstadter Heart Sequences</a>, Complexity, Volume 2017, Article ID 2614163, 8 pages.
%H A004001 B. Balamohan, A. Kuznetsov and S. Tanny, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL10/Tanny/tanny3.html">On the behavior of a variant of Hofstadter's Q-sequence</a>, J. Integer Sequences, Vol. 10 (2007), #07.7.1.
%H A004001 F. Michel Dekking, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Dekking/dekk4.html">Morphisms, Symbolic Sequences, and Their Standard Forms</a>, Journal of Integer Sequences, Vol. 19 (2016), Article 16.1.1.
%H A004001 Nathaniel D. Emerson, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL9/Emerson/emerson6.html">A Family of Meta-Fibonacci Sequences Defined by Variable-Order Recursions</a>, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.8.
%H A004001 Christopher S. Flippen, <a href="https://scholarscompass.vcu.edu/etd/7527/">Minimal Sets, Union-Closed Families, and Frankl's Conjecture</a>, Master's thesis, Virginia Commonwealth Univ., 2023.
%H A004001 Nathan Fox, <a href="https://vimeo.com/141111990">Linear-Recurrent Solutions to Meta-Fibonacci Recurrences, Part 1 (video)</a>, Rutgers Experimental Math Seminar, Oct 01 2015. Part 2 is vimeo.com/141111991.
%H A004001 Nathan Fox, <a href="https://arxiv.org/abs/1611.08244">A Slow Relative of Hofstadter's Q-Sequence</a>, arXiv:1611.08244 [math.NT], 2016.
%H A004001 S. W. Golomb, <a href="/A005185/a005185_1.pdf">Discrete chaos: sequences satisfying "strange" recursions</a>, unpublished manuscript, circa 1990 [cached copy, with permission (annotated)]
%H A004001 J. Grytczuk, <a href="http://dx.doi.org/10.1016/j.disc.2003.10.022">Another variation on Conway's recursive sequence</a>, Discr. Math. 282 (2004), 149-161.
%H A004001 R. K. Guy, <a href="/A005169/a005169_6.pdf">Letter to N. J. A. Sloane</a>, Sep 25 1986.
%H A004001 R. K. Guy, <a href="/A004001/a004001_2.pdf">Letter to N. J. A. Sloane with attachment, 1988</a>
%H A004001 R. K. Guy and N. J. A. Sloane, <a href="/A005180/a005180.pdf">Correspondence</a>, 1988.
%H A004001 Nick Hobson, <a href="/A004001/a004001.py.txt">Python program for this sequence</a>
%H A004001 D. R. Hofstadter, <a href="/A004001/a004001.pdf">Plot of 100000 terms of a(n)-n/2</a>
%H A004001 D. R. Hofstadter, Analogies and Sequences: Intertwined Patterns of Integers and Patterns of Thought Processes, Lecture in DIMACS Conference on Challenges of Identifying Integer Sequences, Rutgers University, Oct 10 2014; <a href="http://vimeo.com/109139374">Part 1</a>, <a href="http://vimeo.com/109139377">Part 2</a>.
%H A004001 A. Isgur, R. Lech, S. Moore, S. Tanny, Y. Verberne, and Y. Zhang, <a href="http://dx.doi.org/10.1137/15M1040505">Constructing New Families of Nested Recursions with Slow Solutions</a>, SIAM J. Discrete Math., 30(2), 2016, 1128-1147. (20 pages); DOI:10.1137/15M1040505.
%H A004001 D. Kleitman, <a href="http://www.jstor.org/stable/2324158">Solution to Problem E3274</a>, Amer. Math. Monthly, 98 (1991), 958-959.
%H A004001 T. Kubo and R. Vakil, <a href="http://dx.doi.org/10.1016/0012-365X(94)00303-Z">On Conway's recursive sequence</a>, Discr. Math. 152 (1996), 225-252.
%H A004001 C. L. Mallows, <a href="http://www.jstor.org/stable/2324028">Conway's challenge sequence</a>, Amer. Math. Monthly, 98 (1991), 5-20.
%H A004001 D. Newman, <a href="http://www.jstor.org/stable/2322766">Problem E3274</a>, Amer. Math. Monthly, 95 (1988), 555.
%H A004001 John A. Pelesko, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Pelesko/pel11.html">Generalizing the Conway-Hofstadter $10,000 Sequence</a>, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.5.
%H A004001 K. Pinn, <a href="http://projecteuclid.org/euclid.em/1046889590">A chaotic cousin of Conway's recursive sequence</a>, Experimental Mathematics, 9:1 (2000), 55-65.
%H A004001 N. J. A. Sloane, <a href="/A004001/a004001_1.pdf">Scan of notebook pages with notes on John Conway's Colloquium talk on Jul 15 1988</a> [See Comments above]
%H A004001 N. J. A. Sloane, <a href="http://neilsloane.com/doc/sg.txt">My favorite integer sequences</a>, in Sequences and their Applications (Proceedings of SETA '98).
%H A004001 I. Vardi, <a href="/A005185/a005185_3.pdf">Email to N. J. A. Sloane, Jun. 1991</a>
%H A004001 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Hofstadter-Conway10000-DollarSequence.html">Hofstadter-Conway 10000-Dollar Sequence.</a>
%H A004001 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Newman-ConwaySequence.html">Newman-Conway Sequence</a>
%H A004001 Wikipedia, <a href="http://en.wikipedia.org/wiki/Hofstadter_sequence">Hofstadter sequence</a>
%H A004001 <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%H A004001 <a href="/index/Ho#Hofstadter">Index entries for Hofstadter-type sequences</a>
%F A004001 Limit_{n->infinity} a(n)/n = 1/2 and as special cases, if n > 0, a(2^n-i) = 2^(n-1) for 0 <= i < = n-1; a(2^n+1) = 2^(n-1) + 1. - _Benoit Cloitre_, Aug 04 2002 [Corrected by _Altug Alkan_, Apr 03 2017]
%e A004001 If n=4, 2^4=16, a(16-i) = 2^(4-1) = 8 for 0 <= i <= 4-1 = 3, hence a(16)=a(15)=a(14)=a(13)=8.
%p A004001 A004001 := proc(n) option remember; if n<=2 then 1 else procname(procname(n-1)) +procname(n-procname(n-1)); fi; end;
%t A004001 a[1] = 1; a[2] = 1; a[n_] := a[n] = a[a[n - 1]] + a[n - a[n - 1]]; Table[ a[n], {n, 1, 75}] (* _Robert G. Wilson v_ *)
%o A004001 (Haskell)
%o A004001 a004001 n = a004001_list !! (n-1)
%o A004001 a004001_list = 1 : 1 : h 3 1  {- memoization -}
%o A004001   where h n x = x' : h (n + 1) x'
%o A004001           where x' = a004001 x + a004001 (n - x)
%o A004001 -- _Reinhard Zumkeller_, Jun 03 2011
%o A004001 (PARI) a=vector(100);a[1]=a[2]=1;for(n=3,#a,a[n]=a[a[n-1]]+a[n-a[n-1]]);a \\ _Charles R Greathouse IV_, Jun 10 2011
%o A004001 (PARI) first(n)=my(v=vector(n)); v[1]=v[2]=1; for(k=3, n, v[k]=v[v[k-1]]+v[k-v[k-1]]); v \\ _Charles R Greathouse IV_, Feb 26 2017
%o A004001 (Scheme)
%o A004001 ;; An implementation of memoization-macro definec can be found for example from: http://oeis.org/wiki/Memoization
%o A004001 (definec (A004001 n) (if (<= n 2) 1 (+ (A004001 (A004001 (- n 1))) (A004001 (- n (A004001 (- n 1)))))))
%o A004001 ;; _Antti Karttunen_, Oct 22 2014
%o A004001 (Python)
%o A004001 def a004001(n):
%o A004001     A = {1: 1, 2: 1}
%o A004001     c = 1 #counter
%o A004001     while n not in A.keys():
%o A004001         if c not in A.keys():
%o A004001             A[c] = A[A[c-1]] + A[c-A[c-1]]
%o A004001         c += 1
%o A004001     return A[n]
%o A004001 # _Edward Minnix III_, Nov 02 2015
%o A004001 (Magma) [n le 2 select 1 else Self(Self(n-1))+ Self(n-Self(n-1)):n in [1..75]]; // _Marius A. Burtea_, Aug 16 2019
%o A004001 (SageMath)
%o A004001 @CachedFunction
%o A004001 def a(n): # a = A004001
%o A004001     if n<3: return 1
%o A004001     else: return a(a(n-1)) + a(n-a(n-1))
%o A004001 [a(n) for n in range(1,101)] # _G. C. Greubel_, Apr 25 2024
%Y A004001 Cf. A005229, A005185, A080677, A088359, A087686, A093879 (first differences), A265332, A266341, A055748 (a chaotic cousin), A188163 (greedy inverse).
%Y A004001 Cf. A004074 (A249071), A005350, A005707, A093878. Different from A086841. Run lengths give A051135.
%Y A004001 Cf. also permutations A267111-A267112 and arrays A265901, A265903.
%K A004001 nonn,easy,nice
%O A004001 1,3
%A A004001 _N. J. A. Sloane_