cp's OEIS Frontend

A005185 Hofstadter Q-sequence: a(1) = a(2) = 1; a(n) = a(n-a(n-1)) + a(n-a(n-2)) for n > 2.

%I A005185 M0438 #259 Jun 23 2025 22:18:12
%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.
%C A005185 _Roman Pearce_, Aug 29 2014, has computed that a(n) exists for n <= 10^10. - _N. J. A. Sloane_
%C A005185 a(n) exists for n <= 3*10^10. - _M. Eric Carr_, Jul 02 2023
%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 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, <a href="/A005185/b005185.txt">Table of n, a(n) for n = 1..10000</a>
%H A005185 Altug Alkan, <a href="https://doi.org/10.1515/math-2018-0124">On a conjecture about generalized Q-recurrence</a>, Open Mathematics, Vol. 16 (2018), pp. 1490-1500.
%H A005185 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 A005185 Altug Alkan, Nathan Fox, and Orhan Ozgur Aybar, <a href="https://www.hindawi.com/journals/complexity/aip/2614163/">On Hofstadter Heart Sequences</a>, Complexity, 2017.
%H A005185 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 A005185 Thomas Bloom, <a href="https://www.erdosproblems.com/422">Problem 422</a>, Erdős Problems.
%H A005185 Paul Bourke, <a href="http://paulbourke.net/fractals/qseries/">Hofstadter "Q" Series</a>.
%H A005185 Paul Bourke, <a href="/A005185/a005185_2.pdf">Hofstadter "Q" Series</a>. [Cached copy, pdf only, with permission]
%H A005185 Paul Bourke, <a href="https://oeis.org/w/images/3/35/A005185.mid">Listen to first 300 terms of this sequence</a>. [Cached copy from the Hofstadter "Q" web page, with permission]
%H A005185 Joseph Callaghan, John J. Chew III, and Stephen M. Tanny, <a href="http://dx.doi.org/10.1137/S0895480103421397">On the behavior of a family of meta-Fibonacci sequences</a>, SIAM Journal on Discrete Mathematics 18.4 (2005): 794-824. See p. 794.
%H A005185 Benoit Cloitre, <a href="/A005185/a005185.png">Plot of a(n)/n - 1/2 for n=1 up to 2^19</a>.
%H A005185 J.-P. Davalan, <a href="http://jeux-et-mathematiques.davalan.org/mots/suites/hof/index-en.html">Douglas Hofstadter's sequences</a>.
%H A005185 Jonathan H. B. Deane and Guido Gentile, <a href="https://arxiv.org/abs/2311.13854">A diluted version of the problem of the existence of the Hofstadter sequence</a>, arXiv:2311.13854 [math.NT], 2023.
%H A005185 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 A005185 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 A005185 Nathan Fox, <a href="https://arxiv.org/abs/1609.06342">Finding Linear-Recurrent Solutions to Hofstadter-Like Recurrences Using Symbolic Computation</a>, arXiv:1609.06342 [math.NT], 2016.
%H A005185 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 A005185 Nathan Fox, <a href="https://arxiv.org/abs/1807.01365">A New Approach to the Hofstadter Q-Recurrence</a>, arXiv:1807.01365 [math.NT], 2018.
%H A005185 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 A005185 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 A005185 R. K. Guy, <a href="/A005169/a005169_6.pdf">Letter to N. J. A. Sloane</a>, Sep 25 1986.
%H A005185 R. K. Guy, <a href="http://www.jstor.org/stable/2323338">Some suspiciously simple sequences</a>, Amer. Math. Monthly 93 (1986), 186-190; 94 (1987), 965; 96 (1989), 905.
%H A005185 Nick Hobson, <a href="/A005185/a005185.py.txt">Python program for this sequence</a>.
%H A005185 D. R. Hofstadter, <a href="/A006336/a006336_1.pdf">Eta-Lore</a>. [Cached copy, with permission]
%H A005185 D. R. Hofstadter, <a href="/A006336/a006336_2.pdf">Pi-Mu Sequences</a>. [Cached copy, with permission]
%H A005185 D. R. Hofstadter and N. J. A. Sloane, <a href="/A006336/a006336.pdf">Correspondence, 1977 and 1991</a>.
%H A005185 D. R. Hofstadter, Curious patterns and non-patterns in a family of meta-Fibonacci recursions, Lecture in Doron Zeilberger's Experimental Mathematics Seminar, Rutgers University, April 10 2014; <a href="https://vimeo.com/91708646">Part 1</a>, <a href="https://vimeo.com/91710600">Part 2</a>.
%H A005185 D. R. Hofstadter, <a href="/A005185/a005185.pdf">Plot of first 100 million terms</a>.
%H A005185 Abraham Isgur, Mustazee Rahman, and Stephen Tanny, <a href="http://dx.doi.org/10.1007/s00026-013-0202-9">Solving non-homogeneous nested recursions using trees</a>, Annals of Combinatorics 17.4 (2013): 695-710. See p. 695. - _N. J. A. Sloane_, Apr 16 2014
%H A005185 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 A005185 Piotr Miska, Bartosz Sobolewski, and Maciej Ulas, <a href="https://arxiv.org/abs/2412.11319">Binary sequences meet the Fibonacci sequence</a>, arXiv:2412.11319 [math.NT], 2024. See p. 20.
%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 href="http://projecteuclid.org/euclid.em/1046889590">A chaotic cousin of Conway's recursive sequence</a>, Experimental Mathematics, 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>, arXiv:cond-mat/9808031 [cond-mat.stat-mech], 1998.
%H A005185 N. J. A. Sloane and Brady Haran, <a href="https://www.youtube.com/watch?v=j0o-pMIR8uk">Amazing Graphs III</a>, Numberphile video (2019).
%H A005185 I. Vardi, <a href="/A005185/a005185_3.pdf">Email to N. J. A. Sloane, Jun. 1991</a>.
%H A005185 A. M. M. Sharif Ullah, <a href="http://dx.doi.org/10.3390/mca22020033">Surface Roughness Modeling Using Q-Sequence</a>, Mathematical and Computational Applications, 2017.
%H A005185 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/HofstadtersQ-Sequence.html">Hofstadter's Q-Sequence</a>.
%H A005185 Wikipedia, <a href="http://en.wikipedia.org/wiki/Hofstadter_sequence">Hofstadter sequence</a>.
%H A005185 Pedro Zanetti, <a href="/A005185/a005185_1.txt">C++ code snippet for this sequence</a>.
%H A005185 <a href="/index/Go#GEB">Index entries for sequences from "Goedel, Escher, Bach"</a>
%H A005185 <a href="/index/Ho#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 A005185 := proc(n) option remember;
%p A005185     if n<=2 then 1
%p A005185     elif n > procname(n-1) and n > procname(n-2) then
%p A005185         RETURN(procname(n-procname(n-1))+procname(n-procname(n-2)));
%p A005185     else
%p A005185         ERROR(" died at n= ", n);
%p A005185     fi; end proc;
%p A005185 # More generally, the following defines the Hofstadter-Huber sequence Q(r,s) - _N. J. A. Sloane_, Apr 15 2014
%p A005185 r:=1; s:=2;
%p A005185 a:=proc(n) option remember; global r,s;
%p A005185 if n <= s then  1
%p A005185 else
%p A005185     if (a(n-r) <= n) and (a(n-s) <= n) then
%p A005185     a(n-a(n-r))+a(n-a(n-s));
%p A005185     else lprint("died with n =",n); return (-1);
%p A005185     fi; fi; end;
%p A005185 [seq(a(n), n=1..100)];
%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,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_, 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 */
%o A005185 (Haskell)
%o A005185 a005185 n = a005185_list !! (n-1)
%o A005185 a005185_list = 1 : 1 : zipWith (+)
%o A005185    (map a005185 $ zipWith (-) [3..] a005185_list)
%o A005185    (map a005185 $ zipWith (-) [3..] $ tail a005185_list)
%o A005185 -- _Reinhard Zumkeller_, Jun 02 2013, Sep 15 2011
%o A005185 (C)
%o A005185 #include <stdio.h>
%o A005185 #define LIM 20
%o A005185 int Qa[LIM];
%o A005185 int Q(int n){if (n==1 || n==2){return 1;} else{return Qa[n-Qa[n-1]]+Qa[n-Qa[n-2]];}}
%o A005185 int main(){int i;printf("n\tQ\n");for(i=1; i<LIM; i+=1){printf("%d\t%d\n", i, Q(i));Qa[i]=Q(i);}printf("\n");} // _Gonzalo Ciruelos_, Aug 01 2013
%o A005185 (Magma) I:=[1,1]; [n le 2 select I[n] else Self(n-Self(n-1))+Self(n-Self(n-2)): n in [1..90]]; // _Vincenzo Librandi_, Aug 08 2014
%o A005185 (Scheme)
%o A005185 ;; An implementation of memoization-macro definec can be found for example in: http://oeis.org/wiki/Memoization
%o A005185 (definec (A005185 n) (if (<= n 2) 1 (+ (A005185 (- n (A005185 (- n 1)))) (A005185 (- n (A005185 (- n 2)))))))
%o A005185 ;; _Antti Karttunen_, Mar 22 2017
%o A005185 (Sage)
%o A005185 @CachedFunction
%o A005185 def a(n):
%o A005185     if (n<3): return 1
%o A005185     else: return a(n -a(n-1)) + a(n -a(n-2))
%o A005185 [a(n) for n in (1..70)] # _G. C. Greubel_, Feb 13 2020
%o A005185 (Python)
%o A005185 from functools import lru_cache
%o A005185 @lru_cache(maxsize=None)
%o A005185 def a(n):
%o A005185     if n < 3: return 1
%o A005185     return a(n - a(n-1)) + a(n - a(n-2))
%o A005185 print([a(n) for n in range(1, 75)]) # _Michael S. Branicky_, Jul 26 2021
%Y A005185 Cf. A004001, A005206, A005374, A005375, A005378.
%Y A005185 Cf. A005379, A070867, A226222, A239913, A284019.
%Y A005185 Cf. A081827 (first differences).
%Y A005185 Cf. A226244, A226245 (record values and where they occur).
%Y A005185 See A244477 for a different start.
%K A005185 nonn,nice,look
%O A005185 1,3
%A A005185 _Simon Plouffe_ and _N. J. A. Sloane_, May 20 1991