%I M0276 #185 Apr 25 2024 13:44:48

%S 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 16,16,16,16,17,18,19,20,21,21,22,23,24,24,25,26,26,27,27,27,28,29,29,

%U 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 Hofstadter-Conway $10000 sequence: a(n) = a(a(n-1)) + a(n-a(n-1)) with a(1) = a(2) = 1.

%C 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 a(n) - a(n-1) = 0 or 1 (see the D. Newman reference). - _Emeric Deutsch_, Jun 06 2005

%C a(A188163(n)) = n and a(m) < n for m < A188163(n). - _Reinhard Zumkeller_, Jun 03 2011

%C From _Daniel Forgues_, Oct 04 2019: (Start)

%C Conjectures:

%C a(n) = n/2 iff n = 2^k, k >= 1.

%C a(n) = 2^(k-1): k times, for n = 2^k - (k-1) to 2^k, k >= 1. (End)

%D 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 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 R. K. Guy, Unsolved Problems Number Theory, Sect. E31.

%D D. R. Hofstadter, personal communication.

%D C. A. Pickover, Wonders of Numbers, "Cards, Frogs and Fractal sequences", Chapter 96, pp. 217-221, Oxford Univ. Press, NY, 2000.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D S. Vajda, Fibonacci and Lucas Numbers and the Golden Section, Wiley, 1989, see p. 129.

%D S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 129.

%H T. D. Noe, <a href="/A004001/b004001.txt">Table of n, a(n) for n = 1..10000</a>

%H 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 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 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 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 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 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 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 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 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 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 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 R. K. Guy, <a href="/A005169/a005169_6.pdf">Letter to N. J. A. Sloane</a>, Sep 25 1986.

%H R. K. Guy, <a href="/A004001/a004001_2.pdf">Letter to N. J. A. Sloane with attachment, 1988</a>

%H R. K. Guy and N. J. A. Sloane, <a href="/A005180/a005180.pdf">Correspondence</a>, 1988.

%H Nick Hobson, <a href="/A004001/a004001.py.txt">Python program for this sequence</a>

%H D. R. Hofstadter, <a href="/A004001/a004001.pdf">Plot of 100000 terms of a(n)-n/2</a>

%H 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 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 D. Kleitman, <a href="http://www.jstor.org/stable/2324158">Solution to Problem E3274</a>, Amer. Math. Monthly, 98 (1991), 958-959.

%H 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 C. L. Mallows, <a href="http://www.jstor.org/stable/2324028">Conway's challenge sequence</a>, Amer. Math. Monthly, 98 (1991), 5-20.

%H D. Newman, <a href="http://www.jstor.org/stable/2322766">Problem E3274</a>, Amer. Math. Monthly, 95 (1988), 555.

%H 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 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 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 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 I. Vardi, <a href="/A005185/a005185_3.pdf">Email to N. J. A. Sloane, Jun. 1991</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Hofstadter-Conway10000-DollarSequence.html">Hofstadter-Conway 10000-Dollar Sequence.</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Newman-ConwaySequence.html">Newman-Conway Sequence</a>

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Hofstadter_sequence">Hofstadter sequence</a>

%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>

%H <a href="/index/Ho#Hofstadter">Index entries for Hofstadter-type sequences</a>

%F 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 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 := proc(n) option remember; if n<=2 then 1 else procname(procname(n-1)) +procname(n-procname(n-1)); fi; end;

%t 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 (Haskell)

%o a004001 n = a004001_list !! (n-1)

%o a004001_list = 1 : 1 : h 3 1 {- memoization -}

%o where h n x = x' : h (n + 1) x'

%o where x' = a004001 x + a004001 (n - x)

%o -- _Reinhard Zumkeller_, Jun 03 2011

%o (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 (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 (Scheme)

%o ;; An implementation of memoization-macro definec can be found for example from: http://oeis.org/wiki/Memoization

%o (definec (A004001 n) (if (<= n 2) 1 (+ (A004001 (A004001 (- n 1))) (A004001 (- n (A004001 (- n 1)))))))

%o ;; _Antti Karttunen_, Oct 22 2014

%o (Python)

%o def a004001(n):

%o A = {1: 1, 2: 1}

%o c = 1 #counter

%o while n not in A.keys():

%o if c not in A.keys():

%o A[c] = A[A[c-1]] + A[c-A[c-1]]

%o c += 1

%o return A[n]

%o # _Edward Minnix III_, Nov 02 2015

%o (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 (SageMath)

%o @CachedFunction

%o def a(n): # a = A004001

%o if n<3: return 1

%o else: return a(a(n-1)) + a(n-a(n-1))

%o [a(n) for n in range(1,101)] # _G. C. Greubel_, Apr 25 2024

%Y Cf. A005229, A005185, A080677, A088359, A087686, A093879 (first differences), A265332, A266341, A055748 (a chaotic cousin), A188163 (greedy inverse).

%Y Cf. A004074 (A249071), A005350, A005707, A093878. Different from A086841. Run lengths give A051135.

%Y Cf. also permutations A267111-A267112 and arrays A265901, A265903.

%K nonn,easy,nice

%O 1,3

%A _N. J. A. Sloane_