%I A005185 M0438
%S A005185 1,1,2,3,3,4,5,5,6,6,6,8,8,8,10,9,10,11,11,12,12,12,12,16,14,14,16,16,
%T A005185 16,16,20,17,17,20,21,19,20,22,21,22,23,23,24,24,24,24,24,32,24,25,30,
%U A005185 28,26,30,30,28,32,30,32,32,32,32,40,33,31,38,35,33,39,40,37,38,40,39
%N A005185 Hofstadter Q-sequence: a(1) = a(2) = 1; a(n)=a(n-a(n-1))+a(n-a(n-2)) 
               for n > 2.
%C A005185 Rate of growth is not known. In fact it is not even known if this sequence 
               is defined for all positive n.
%D A005185 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 A005185 Nathaniel D. Emerson, A Family of Meta-Fibonacci Sequences Defined by 
               Variable-Order Recursions, Journal of Integer Sequences, Vol. 9 (2006), 
               Article 06.1.8.
%D A005185 J. Grytczuk, Another variation on Conway's recursive sequence, Discr. 
               Math. 282 (2004), 149-161.
%D A005185 R. K. Guy, Some suspiciously simple sequences, Amer. Math. Monthly 93 
               (1986), 186-190; 94 (1987), 965; 96 (1989), 905.
%D A005185 R. K. Guy, Unsolved Problems in Number Theory, Sect. E31.
%D A005185 D. R. Hofstadter, Goedel, Escher, Bach: an Eternal Golden Braid, Random 
               House, 1980, p. 138.
%D A005185 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%D A005185 S. Vajda, Fibonacci and Lucas Numbers and the Golden Section, Wiley, 
               1989, see p. 129.
%D A005185 S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 129.
%H A005185 T. D. Noe and N. J. A. Sloane (njas(AT)research.att.com), <a href="b005185.txt">
               Table of n, a(n) for n=1..10000</a>
%H A005185 B. Balamohan, A. Kuznetsov and S. Tanny, <a href="http://www.cs.uwaterloo.ca/
               journals/JIS/index.html">On the behavior of a variant of Hofstadter's 
               Q-sequence</a>, J. Integer Sequences, Vol. 10 (2007), #07.7.1.
%H A005185 P. Bourke, <a href="http://astronomy.swin.edu.au/~pbourke/fractals/qseries">
               Hofstadter "Q" Series</a>
%H A005185 J.-P. Davalan, <a href="http://perso.wanadoo.fr/jean-paul.davalan/mots/
               suites/hof/index-en.html">Douglas Hofstadter's sequences</a>
%H A005185 R. K. Guy, <a href="http://gotmath.com/guy.pdf">Hofstadter's Meta-Fibonacci 
               sequence</a>, Amer. Math. Monthly, 93(3) 186-187 1986. [Broken link]
%H A005185 Nick Hobson, <a href="a005185.py.txt">Python program for this sequence</
               a>
%H A005185 K. Pinn, <a href="http://arXiv.org/abs/chao-dyn/9803012">Order and chaos 
               in Hofstadter's Q(n) sequence</a>, Complexity, 4:3 (1999), 41-46.
%H A005185 K. Pinn, A chaotic cousin of Conway's recursive sequence, <a href="http:/
               /www.expmath.org/expmath/">Experimental Mathematics</a>, 9:1 (2000), 
               55-65.
%H A005185 K. Pinn, <a href="http://arXiv.org/abs/cond-mat/9808031">A Chaotic Cousin 
               Of Conway's Recursive Sequence</a>
%H A005185 T. Sillke, <a href="http://www.mathematik.uni-bielefeld.de/~sillke/SEQUENCES/
               series012">Hofstadter Sequence</a>
%H A005185 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
               HofstadtersQ-Sequence.html">Link to a section of The World of Mathematics.</
               a>
%H A005185 <a href="Sindx_Go.html#GEB">Index entries for sequences from "Goedel, 
               Escher, Bach"</a>
%H A005185 <a href="Sindx_Ho.html#Hofstadter">Index entries for Hofstadter-type 
               sequences</a>
%e A005185 a(18) = 11 because a(17) is 10 and a(16) is 9, so we take a(18 - 10) 
               + a(18 - 9) = a(8) + a(9) = 5 + 6 = 11
%p A005185 a := proc(n) option remember; if n<=2 then 1 else if n > a(n-1) and n 
               > a(n-2) then RETURN(a(n-a(n-1))+a(n-a(n-2))); else ERROR(" died 
               at n= ", n); fi; fi; end;
%t A005185 a[1] = a[2] = 1; a[n_] := a[n] = a[n - a[n - 1]] + a[n - a[n - 2]]; Table[ 
               a[n], {n, 1, 70} ]
%o A005185 (Scheme): (define q (lambda (n) (cond ( (eqv? n 0) 1) ( (eqv? n 1) 1) 
               ( #t (+ (q (- n (q (- n 1)))) (q (- n (q (- n 2)))))))))
%o A005185 (Mupad) q:=proc(n) option remember; begin if n<=2 then 1 else q(n-q(n-1))+q(n-q(n-2)) 
               end_if; end_proc: q(i)$i=1..100; - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), 
               Apr 03 2007
%o A005185 (PARI) {a(n)= local(A); if(n<1, 0, A=vector(n,k,1); for(k=3, n, A[k]= 
               A[k-A[k-1]]+ A[k-A[k-2]]); A[n])} /* Michael Somos Jul 16 2007 */
%Y A005185 Cf. A004001, A005206, A005374, A005375, A005378, A005379.
%Y A005185 Sequence in context: A080595 A123579 A166493 this_sequence A119466 A100922 
               A047785
%Y A005185 Adjacent sequences: A005182 A005183 A005184 this_sequence A005186 A005187 
               A005188
%K A005185 nonn,nice,easy
%O A005185 1,3
%A A005185 Simon Plouffe, N. J. A. Sloane (njas(AT)research.att.com).