A244477 -id:A244477 - 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.

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, 16, 16, 20, 17, 17, 20, 21, 19, 20, 22, 21, 22, 23, 23, 24, 24, 24, 24, 24, 32, 24, 25, 30, 28, 26, 30, 30, 28, 32, 30, 32, 32, 32, 32, 40, 33, 31, 38, 35, 33, 39, 40, 37, 38, 40, 39

Offset: 1

Simon Plouffe and N. J. A. Sloane, May 20 1991

Rate of growth is not known. In fact it is not even known if this sequence is defined for all positive n.
Roman Pearce, Aug 29 2014, has computed that a(n) exists for n <= 10^10. - N. J. A. Sloane
a(n) exists for n <= 3*10^10. - M. Eric Carr, Jul 02 2023

			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.

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.
R. K. Guy, Unsolved Problems in Number Theory, Sect. E31.
D. R. Hofstadter, Goedel, Escher, Bach: an Eternal Golden Braid, Random House, 1980, p. 138.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
S. Vajda, Fibonacci and Lucas Numbers and the Golden Section, Wiley, 1989, see p. 129.
S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 129.

T. D. Noe and N. J. A. Sloane, Table of n, a(n) for n = 1..10000
Altug Alkan, On a conjecture about generalized Q-recurrence, Open Mathematics, Vol. 16 (2018), pp. 1490-1500.
Altug Alkan, On a Generalization of Hofstadter's Q-Sequence: A Family of Chaotic Generational Structures, Complexity (2018) Article ID 8517125.
Altug Alkan, Nathan Fox, and Orhan Ozgur Aybar, On Hofstadter Heart Sequences, Complexity, 2017.
B. Balamohan, A. Kuznetsov, and S. Tanny, On the behavior of a variant of Hofstadter's Q-sequence, J. Integer Sequences, Vol. 10 (2007), #07.7.1.
Thomas Bloom, Problem 422, Erdős Problems.
Paul Bourke, Hofstadter "Q" Series.
Paul Bourke, Hofstadter "Q" Series. [Cached copy, pdf only, with permission]
Paul Bourke, Listen to first 300 terms of this sequence. [Cached copy from the Hofstadter "Q" web page, with permission]
Joseph Callaghan, John J. Chew III, and Stephen M. Tanny, On the behavior of a family of meta-Fibonacci sequences, SIAM Journal on Discrete Mathematics 18.4 (2005): 794-824. See p. 794.
Benoit Cloitre, Plot of a(n)/n - 1/2 for n=1 up to 2^19.
J.-P. Davalan, Douglas Hofstadter's sequences.
Jonathan H. B. Deane and Guido Gentile, A diluted version of the problem of the existence of the Hofstadter sequence, arXiv:2311.13854 [math.NT], 2023.
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.
Nathan Fox, Linear-Recurrent Solutions to Meta-Fibonacci Recurrences, Part 1 (video), Rutgers Experimental Math Seminar, Oct 01 2015. Part 2 is vimeo.com/141111991.
Nathan Fox, Finding Linear-Recurrent Solutions to Hofstadter-Like Recurrences Using Symbolic Computation, arXiv:1609.06342 [math.NT], 2016.
Nathan Fox, A Slow Relative of Hofstadter's Q-Sequence, arXiv:1611.08244 [math.NT], 2016.
Nathan Fox, A New Approach to the Hofstadter Q-Recurrence, arXiv:1807.01365 [math.NT], 2018.
S. W. Golomb, Discrete chaos: sequences satisfying "strange" recursions, unpublished manuscript, circa 1990 [cached copy, with permission (annotated)].
J. Grytczuk, Another variation on Conway's recursive sequence, Discr. Math. 282 (2004), 149-161.
R. K. Guy, Letter to N. J. A. Sloane, Sep 25 1986.
R. K. Guy, Some suspiciously simple sequences, Amer. Math. Monthly 93 (1986), 186-190; 94 (1987), 965; 96 (1989), 905.
Nick Hobson, Python program for this sequence.
D. R. Hofstadter, Eta-Lore. [Cached copy, with permission]
D. R. Hofstadter, Pi-Mu Sequences. [Cached copy, with permission]
D. R. Hofstadter and N. J. A. Sloane, Correspondence, 1977 and 1991.
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; Part 1, Part 2.
D. R. Hofstadter, Plot of first 100 million terms.
Abraham Isgur, Mustazee Rahman, and Stephen Tanny, Solving non-homogeneous nested recursions using trees, Annals of Combinatorics 17.4 (2013): 695-710. See p. 695. - _N. J. A. Sloane_, Apr 16 2014
A. Isgur, R. Lech, S. Moore, S. Tanny, Y. Verberne, and Y. Zhang, Constructing New Families of Nested Recursions with Slow Solutions, SIAM J. Discrete Math., 30(2), 2016, 1128-1147. (20 pages); DOI:10.1137/15M1040505.
Piotr Miska, Bartosz Sobolewski, and Maciej Ulas, Binary sequences meet the Fibonacci sequence, arXiv:2412.11319 [math.NT], 2024. See p. 20.
K. Pinn, Order and chaos in Hofstadter's Q(n) sequence, Complexity, 4:3 (1999), 41-46.
K. Pinn, A chaotic cousin of Conway's recursive sequence, Experimental Mathematics, 9:1 (2000), 55-65.
K. Pinn, A Chaotic Cousin Of Conway's Recursive Sequence, arXiv:cond-mat/9808031 [cond-mat.stat-mech], 1998.
N. J. A. Sloane and Brady Haran, Amazing Graphs III, Numberphile video (2019).
I. Vardi, Email to N. J. A. Sloane, Jun. 1991.
A. M. M. Sharif Ullah, Surface Roughness Modeling Using Q-Sequence, Mathematical and Computational Applications, 2017.
Eric Weisstein's World of Mathematics, Hofstadter's Q-Sequence.
Wikipedia, Hofstadter sequence.
Pedro Zanetti, C++ code snippet for this sequence.
Index entries for sequences from "Goedel, Escher, Bach"
Index entries for Hofstadter-type sequences

Cf. A004001, A005206, A005374, A005375, A005378.
Cf. A005379, A070867, A226222, A239913, A284019.
Cf. A081827 (first differences).
Cf. A226244, A226245 (record values and where they occur).
See A244477 for a different start.

#include 
#define LIM 20
int Qa[LIM];
int Q(int n){if (n==1 || n==2){return 1;} else{return Qa[n-Qa[n-1]]+Qa[n-Qa[n-2]];}}
int main(){int i;printf("n\tQ\n");for(i=1; iGonzalo Ciruelos, Aug 01 2013

a005185 n = a005185_list !! (n-1)
a005185_list = 1 : 1 : zipWith (+)
   (map a005185 $ zipWith (-) [3..] a005185_list)
   (map a005185 $ zipWith (-) [3..] $ tail a005185_list)
-- Reinhard Zumkeller, Jun 02 2013, Sep 15 2011

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

A005185 := proc(n) option remember;
    if n<=2 then 1
    elif n > procname(n-1) and n > procname(n-2) then
        RETURN(procname(n-procname(n-1))+procname(n-procname(n-2)));
    else
        ERROR(" died at n= ", n);
    fi; end proc;
# More generally, the following defines the Hofstadter-Huber sequence Q(r,s) - N. J. A. Sloane, Apr 15 2014
r:=1; s:=2;
a:=proc(n) option remember; global r,s;
if n <= s then  1
else
    if (a(n-r) <= n) and (a(n-s) <= n) then
    a(n-a(n-r))+a(n-a(n-s));
    else lprint("died with n =",n); return (-1);
    fi; fi; end;
[seq(a(n), n=1..100)];

a[1]=a[2]=1; a[n_]:= a[n]= a[n -a[n-1]] + a[n -a[n-2]]; Table[ a[n], {n,70}]

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

{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 */

from functools import lru_cache
@lru_cache(maxsize=None)
def a(n):
    if n < 3: return 1
    return a(n - a(n-1)) + a(n - a(n-2))
print([a(n) for n in range(1, 75)]) # Michael S. Branicky, Jul 26 2021

@CachedFunction
def a(n):
    if (n<3): return 1
    else: return a(n -a(n-1)) + a(n -a(n-2))
[a(n) for n in (1..70)] # G. C. Greubel, Feb 13 2020

(define q (lambda (n) (cond ( (eqv? n 0) 1) ( (eqv? n 1) 1) ( #t (+ (q (- n (q (- n 1)))) (q (- n (q (- n 2)))))))))

;; An implementation of memoization-macro definec can be found for example in: http://oeis.org/wiki/Memoization
(definec (A005185 n) (if (<= n 2) 1 (+ (A005185 (- n (A005185 (- n 1)))) (A005185 (- n (A005185 (- n 2)))))))
;; Antti Karttunen, Mar 22 2017

A264756 An eventually quasilinear solution to Hofstadter's Q recurrence.

Original entry on oeis.org

1, 0, 3, 3, 2, 6, 3, 2, 9, 3, 2, 12, 3, 2, 15, 3, 2, 18, 3, 2, 21, 3, 2, 24, 3, 2, 27, 3, 2, 30, 3, 2, 33, 3, 2, 36, 3, 2, 39, 3, 2, 42, 3, 2, 45, 3, 2, 48, 3, 2, 51, 3, 2, 54, 3, 2, 57, 3, 2, 60, 3, 2, 63, 3, 2, 66, 3, 2, 69, 3, 2, 72, 3, 2, 75, 3, 2, 78, 3, 2, 81

Offset: 1

Nathan Fox, Nov 23 2015

a(n) is the solution to the recurrence relation a(n) = a(n-a(n-1)) +a(n-a(n-2)) [Hofstadter's Q recurrence], with the initial conditions: a(n) = 0 if n <= 0; a(1) = 1, a(2) = 0, a(3) = 3, a(4) = 3, a(5) = 2.

Colin Barker, Table of n, a(n) for n = 1..1000
Nathan Fox, Quasipolynomial Solutions to the Hofstadter Q-Recurrence, arXiv preprint arXiv:1511.06484 [math.NT], 2015.
Nathan Fox, Finding Linear-Recurrent Solutions to Hofstadter-Like Recurrences Using Symbolic Computation, arXiv:1609.06342 [math.NT], 2016.
Index entries for linear recurrences with constant coefficients, signature (0,0,2,0,0,-1).

Cf. A005185, A188670, A244477, A264757, A264758.

[1,0] cat [2+(n-3)*(1+Floor(-n/3)+Floor(n/3))-Floor(-(n+1)/3)-Floor((n+1)/3): n in [3..100]]; // Vincenzo Librandi, Nov 25 2015

CoefficientList[Series[-(2*x^7 + 2*x^6 - 2*x^4 - x^3 - 3*x^2 - 1)/((x - 1)^2*(x^2 + x + 1)^2), {x, 0, 100}], x] (* Wesley Ivan Hurt, Nov 24 2015 *)
Join[{1, 0}, LinearRecurrence[{0, 0, 2, 0, 0, -1}, {3, 3, 2, 6, 3, 2}, 100]] (* Vincenzo Librandi, Nov 25 2015 *)

Vec(-x*(2*x^7+2*x^6-2*x^4-x^3-3*x^2-1)/((x-1)^2*(x^2+x+1)^2) + O(x^100)) \\ Colin Barker, Nov 23 2015

a(1) = 1, a(2) = 0; thereafter a(3n) = 3n, a(3n+1) = 3, a(3n+2) = 2.
From Colin Barker, Nov 23 2015: (Start)
a(n) = 2*a(n-3) - a(n-6) for n>8.
G.f.: -x*(2*x^7+2*x^6-2*x^4-x^3-3*x^2-1) / ((x-1)^2*(x^2+x+1)^2).
(End)
a(1) = 1, a(2) = 0, a(n) = 2 + (n-3)*(1 + floor(-n/3) + floor(n/3)) - floor(-(n+1)/3) - floor((n+1)/3) for n>2. - Wesley Ivan Hurt, Nov 24 2015

A264757 An eventually quasi-quadratic solution to Hofstadter's Q recurrence.

Original entry on oeis.org

4, 0, 5, 6, 2, 6, 6, 3, 11, 6, 2, 12, 6, 3, 23, 6, 2, 18, 6, 3, 41, 6, 2, 24, 6, 3, 65, 6, 2, 30, 6, 3, 95, 6, 2, 36, 6, 3, 131, 6, 2, 42, 6, 3, 173, 6, 2, 48, 6, 3, 221, 6, 2, 54, 6, 3, 275, 6, 2, 60, 6, 3, 335, 6, 2, 66, 6, 3, 401, 6, 2, 72, 6, 3, 473, 6

Offset: 1

Nathan Fox, Nov 23 2015

a(n) is the solution to the recurrence relation a(n) = a(n-a(n-1)) + a(n-a(n-2)) [Hofstadter's Q recurrence], with the initial conditions: a(n) = 0 if n <= 0; a(1) = 4, a(2) = 0, a(3) = 5, a(4) = 6, a(5) = 2, a(6) = 6, a(7) = 6, a(8) = 3.

Colin Barker, Table of n, a(n) for n = 1..1000
Nathan Fox, Quasipolynomial Solutions to the Hofstadter Q-Recurrence, arXiv preprint arXiv:1511.06484 [math.NT], 2015.
Index entries for linear recurrences with constant coefficients, signature (0,0,0,0,0,3,0,0,0,0,0,-3,0,0,0,0,0,1).

Cf. A005185, A188670, A244477, A264756, A264758.

Table[If[n < 3, # - n - 1, #] &@ Switch[Mod[n, 6], 0, n, 1, 6, 2, 3, 3, 3 #^2 + 3 # + 5 &[(n - 3)/6], 4, 6, 5, 2], {n, 75}] (* or *)
Rest@ CoefficientList[Series[x (4 + 5 x^2 + 6 x^3 + 2 x^4 + 6 x^5 - 6 x^6 + 3 x^7 - 4 x^8 - 12 x^9 - 4 x^10 - 6 x^11 - 6 x^13 + 5 x^14 + 6 x^15 + 2 x^16 + 2 x^18 + 3 x^19)/((1 - x)^3*(1 + x)^3*(1 - x + x^2)^3*(1 + x + x^2)^3), {x, 0, 76}], x] (* Michael De Vlieger, Nov 14 2016 *)

Vec(x*(4+5*x^2+6*x^3+2*x^4+6*x^5-6*x^6+3*x^7-4*x^8-12*x^9-4*x^10-6*x^11-6*x^13+5*x^14+6*x^15+2*x^16+2*x^18+3*x^19)/((1-x)^3*(1+x)^3*(1-x+x^2)^3*(1+x+x^2)^3) + O(x^100)) \\ Colin Barker, Nov 14 2016

a(1) = 4, a(2) = 0; thereafter a(6*n) = 6*n, a(6*n+1) = 6, a(6*n+2) = 3, a(6*n+3) = 3*n^2+3*n+5, a(6*n+4) = 6, a(6*n+5) = 2.
From Colin Barker, Nov 14 2016: (Start)
G.f.: x*(4 + 5*x^2 + 6*x^3 + 2*x^4 + 6*x^5 - 6*x^6 + 3*x^7 - 4*x^8 - 12*x^9 - 4*x^10 - 6*x^11 - 6*x^13 + 5*x^14 + 6*x^15 + 2*x^16 + 2*x^18 + 3*x^19) / ((1 - x)^3 * (1 + x)^3 * (1 - x + x^2)^3 * (1 + x + x^2)^3).
a(n) = 3*a(n-6) - 3*a(n-12) + a(n-18) for n>20.
(End)

A264758 An eventually quasi-cubic solution to Hofstadter's Q recurrence.

Original entry on oeis.org

7, 0, 5, 9, 3, 8, 9, 2, 9, 9, 3, 14, 9, 3, 22, 9, 2, 18, 9, 3, 32, 9, 3, 54, 9, 2, 27, 9, 3, 59, 9, 3, 113, 9, 2, 36, 9, 3, 95, 9, 3, 208, 9, 2, 45, 9, 3, 140, 9, 3, 348, 9, 2, 54, 9, 3, 194, 9, 3, 542, 9, 2, 63, 9, 3, 257, 9, 3, 799, 9, 2, 72, 9, 3, 329, 9

Offset: 1

Nathan Fox, Nov 23 2015

a(n) is the solution to the recurrence relation a(n) = a(n-a(n-1)) + a(n-a(n-2)) [Hofstadter's Q recurrence], with the initial conditions: a(n) = 0 if n <= 0; a(1) = 7, a(2) = 0, a(3) = 5, a(4) = 9, a(5) = 3, a(6) = 8, a(7) = 9, a(8) = 2, a(9) = 9, a(10) = 9, a(11) = 3.

Colin Barker, Table of n, a(n) for n = 1..1000
Nathan Fox, Quasipolynomial Solutions to the Hofstadter Q-Recurrence, arXiv preprint arXiv:1511.06484 [math.NT], 2015.
Index entries for linear recurrences with constant coefficients, signature (0,0,0,0,0,0,0,0,4,0,0,0,0,0,0,0,0,-6,0,0,0,0,0,0,0,0,4,0,0,0,0,0,0,0,0,-1).

Cf. A005185, A188670, A244477, A264756, A264757.

CoefficientList[Series[x (7+5x^2+9x^3+3x^4+8x^5+9x^6+2x^7+9x^8- 19x^9+ 3x^10- 6x^11- 27x^12-9x^13- 10x^14- 27x^15-6x^16-18x^17+ 15x^18- 9x^19+6x^20+ 27x^21+9x^22+14x^23+ 27x^24+ 6x^25+ 9x^26-x^27+9x^28- 5x^29-9x^30-3x^31- 3x^32-9x^33-2x^34- 2x^36-3x^37)/((1-x)^4(1+x+x^2)^4 (1+x^3+x^6)^4),{x,0,100}],x] (* Harvey P. Dale, Aug 14 2021 *)

a = [7,0,5,9,3,8,9,2]; for(n=1, 10, a=concat(a, [9*n, 9, 3, 9/2*n^2+9/2*n+5, 9, 3, 3/2*n^3+9/2*n^2+8*n+8, 9, 2])); a

a(1) = 7, a(2) = 0; thereafter a(9*n) = 9*n, a(9*n+1) = 9, a(9*n+2) = 3, a(9*n+3) = 9/2*n^2+9/2*n+5, a(9*n+4) = 9, a(9*n+5) = 3, a(9*n+6) = 3/2*n^3+9/2*n^2+8*n+8, a(9*n+7) = 9, a(9*n+8) = 2.
From Colin Barker, Nov 14 2016: (Start)
G.f.: x*(7 +5*x^2 +9*x^3 +3*x^4 +8*x^5 +9*x^6 +2*x^7 +9*x^8 -19*x^9 +3*x^10 -6*x^11 -27*x^12 -9*x^13 -10*x^14 -27*x^15 -6*x^16 -18*x^17 +15*x^18 -9*x^19 +6*x^20 +27*x^21 +9*x^22 +14*x^23 +27*x^24 +6*x^25 +9*x^26 -x^27 +9*x^28 -5*x^29 -9*x^30 -3*x^31 -3*x^32 -9*x^33 -2*x^34 -2*x^36 -3*x^37) / ((1 -x)^4*(1 +x +x^2)^4*(1 +x^3 +x^6)^4).
a(n) = 4*a(n-9) - 6*a(n-18) + 4*a(n-27) - a(n-36) for n>38.
(End)

A268368 An eventually quasi-quadratic sequence satisfying a Hofstadter-like recurrence.

Original entry on oeis.org

0, 1, 0, 4, 4, 4, 3, 12, 8, 4, 3, 24, 12, 4, 3, 40, 16, 4, 3, 60, 20, 4, 3, 84, 24, 4, 3, 112, 28, 4, 3, 144, 32, 4, 3, 180, 36, 4, 3, 220, 40, 4, 3, 264, 44, 4, 3, 312, 48, 4, 3, 364, 52, 4, 3, 420, 56, 4, 3, 480, 60, 4, 3, 544, 64, 4, 3, 612, 68, 4, 3, 684

Offset: 1

Nathan Fox, Feb 23 2016

a(n) is the solution to the recurrence relation a(n) = a(n-a(n-1)) + a(n-a(n-2)) + a(n-a(n-3)), with the initial conditions: a(n) = 0 if n <= 0; a(1) = 0, a(2) = 1, a(3) = 0, a(4) = 4, a(5) = 4, a(6) = 4, a(7) = 3.

Colin Barker, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (0,0,0,3,0,0,0,-3,0,0,0,1).

Cf. A005185, A188670, A244477, A264757, A267501.

concat(0, Vec(x^2*(1 + 4*x^2 + 4*x^3 + x^4 + 3*x^5 - 4*x^7 - 5*x^8 - 6*x^9 + 3*x^12 + 3*x^13) / ((1 - x)^3*(1 + x)^3*(1 + x^2)^3) + O(x^100))) \\ Colin Barker, Jun 22 2017

a(2) = 1, a(3) = 0; otherwise a(4n) = 2n^2+2n, a(4n+1) = 4n, a(4n+2) = 4, a(4n+3) = 3.
From Colin Barker, Jun 22 2017: (Start)
G.f.: x^2*(1 + 4*x^2 + 4*x^3 + x^4 + 3*x^5 - 4*x^7 - 5*x^8 - 6*x^9 + 3*x^12 + 3*x^13) / ((1 - x)^3*(1 + x)^3*(1 + x^2)^3).
a(n) = 3*a(n-4) - 3*a(n-8) + a(n-12) for n>12.
(End)

A296518 a(1) = 3, a(2) = a(5) = 1, a(3) = a(4) = a(6) = 2; a(n) = a(n-a(n-1)) + a(n-a(n-2)) + a(n-a(n-3)) for n > 6.

Original entry on oeis.org

3, 1, 2, 2, 1, 2, 4, 8, 8, 4, 8, 12, 12, 4, 12, 16, 16, 4, 16, 20, 20, 4, 20, 24, 24, 4, 24, 28, 28, 4, 28, 32, 32, 4, 32, 36, 36, 4, 36, 40, 40, 4, 40, 44, 44, 4, 44, 48, 48, 4, 48, 52, 52, 4, 52, 56, 56, 4, 56, 60, 60, 4, 60, 64, 64, 4, 64, 68, 68, 4, 68, 72, 72, 4, 72, 76, 76, 4, 76, 80, 80, 4, 80, 84, 84, 4, 84, 88, 88, 4

Offset: 1

Altug Alkan, Dec 14 2017

A quasi-periodic solution to the three-term Hofstadter recurrence a(n) = a(n-a(n-1)) + a(n-a(n-2)) + a(n-a(n-3)). For a quasi-quadratic solution, see also A268368 that uses the convention that evaluating at a nonpositive index gives zero (this sequence and A244477 do not use this convention). See page 119 at the Fox reference for the detailed analysis of solutions with initial conditions with 1 through N. The three-term Hofstadter recurrence also has a slow solution (A278055) and chaotic solutions such as A292351, A296413 and A296440. So the recurrence a(n) = a(n-a(n-1)) + a(n-a(n-2)) + a(n-a(n-3)) has all known types of behaviors that are mentioned on page 7 of the Tanny reference in the Links section.

Colin Barker, Table of n, a(n) for n = 1..1000
Altug Alkan, On a conjecture about generalized Q-recurrence, Open Mathematics (2018) Vol. 16, Issue 1, 1490-1500.
Nathan Fox, An exploration of nested recurrences using experimental mathematics, Ph.D. thesis, 2017 (19 MB).
Steve Tanny, An Invitation to Nested Recurrence Relations, Slides of talk presented at CanaDAM 2013.
Index entries for linear recurrences with constant coefficients, signature (0,0,0,2,0,0,0,-1).

Cf. A005185, A244477, A268368, A278055, A296413, A296440.

a:= proc(n) option remember; procname(n-procname(n-1))+procname(n-procname(n-2))+procname(n-procname(n-3)) end proc:
a(1):= 3: a(2):= 1: a(3):= 2: a(4):= 2: a(5):= 1: a(6):= 2:
map(a, [$1..100]); # after Robert Israel at A296440

Fold[Append[#1, #1[[#2 - #1[[#2 - 1]] ]] + #1[[#2 - #1[[#2 - 2]] ]] + #1[[#2 - #1[[#2 - 3]] ]] ] &, {3, 1, 2, 2, 1, 2}, Range[7, 90]] (* or *)
Rest@ CoefficientList[Series[x (3 + x + 2 x^2 + 2 x^3 - 5 x^4 + 4 x^7 + 9 x^8 + x^9 + 2 x^10 - 2 x^11 - 3 x^12 - 2 x^13)/((1 - x)^2*(1 + x)^2*(1 + x^2)^2), {x, 0, 90}], x] (* Michael De Vlieger, Dec 14 2017 *)
LinearRecurrence[{0,0,0,2,0,0,0,-1},{3,1,2,2,1,2,4,8,8,4,8,12,12,4},100] (* Harvey P. Dale, May 30 2018 *)

my(q=vector(100)); q[1]=3;q[2]=1;q[3]=2;q[4]=2;q[5]=1;q[6]=2;for(n=7, #q, q[n] = q[n-q[n-1]]+q[n-q[n-2]]+q[n-q[n-3]]); q

Vec(x*(3 + x + 2*x^2 + 2*x^3 - 5*x^4 + 4*x^7 + 9*x^8 + x^9 + 2*x^10 - 2*x^11 - 3*x^12 - 2*x^13) / ((1 - x)^2*(1 + x)^2*(1 + x^2)^2) + O(x^100)) \\ Colin Barker, Dec 14 2017

;; With memoization-macro definec.
(definec (A296518 n) (cond ((= 1 n) 3) ((or (= 2 n) (= 5 n)) 1) ((<= n 6) 2) (else (+ (A296518 (- n (A296518 (- n 1)))) (A296518 (- n (A296518 (- n 2)))) (A296518 (- n (A296518 (- n 3)))))))) ;; Antti Karttunen, Dec 16 2017

a(4*k) = a(4*k+1) = a(4*k+3) = 4*k, a(4*k+2) = 4 for k > 1.
From Colin Barker, Dec 14 2017: (Start)
G.f.: x*(3 + x + 2*x^2 + 2*x^3 - 5*x^4 + 4*x^7 + 9*x^8 + x^9 + 2*x^10 - 2*x^11 - 3*x^12 - 2*x^13) / ((1 - x)^2*(1 + x)^2*(1 + x^2)^2).
a(n) = 2*a(n-4) - a(n-8) for n > 14.
(End)

A309492 a(1) = a(2) = 1, a(3) = 3, a(4) = 5, a(5) = 2; a(n) = a(n-a(n-2)) + a(n-a(n-3)) for n > 5.

Original entry on oeis.org

1, 1, 3, 5, 2, 4, 3, 9, 6, 4, 3, 13, 10, 4, 3, 17, 14, 4, 3, 21, 18, 4, 3, 25, 22, 4, 3, 29, 26, 4, 3, 33, 30, 4, 3, 37, 34, 4, 3, 41, 38, 4, 3, 45, 42, 4, 3, 49, 46, 4, 3, 53, 50, 4, 3, 57, 54, 4, 3, 61, 58, 4, 3, 65, 62, 4, 3, 69, 66, 4, 3, 73, 70, 4, 3, 77, 74, 4, 3, 81, 78, 4, 3, 85, 82, 4, 3

Offset: 1

Altug Alkan, Aug 04 2019

A well-defined solution sequence for recurrence a(n) = a(n-a(n-2)) + a(n-a(n-3)).

Colin Barker, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (1,-1,1,1,-1,1,-1).

Cf. A063892, A244477.

I:=[1,1,3,5,2];[n le 5 select I[n] else Self(n-Self(n-2))+Self(n-Self(n-3)): n in [1..90]]; // Marius A. Burtea, Aug 07 2019

a[n_] := a[n] = If[n < 6, {1, 1, 3, 5, 2}[[n]], a[n - a[n-2]] + a[n - a[n-3]]]; Array[a, 87] (* Giovanni Resta, Aug 07 2019 *)

q=vector(100); q[1]=1;q[2]=1;q[3]=3;q[4]=5;q[5]=2; for(n=6, #q, q[n]=q[n-q[n-2]]+q[n-q[n-3]]); q

Vec(x*(1 + 3*x^2 + 2*x^3 - 2*x^4 + 4*x^5 - 7*x^6 + 6*x^7 - 3*x^8) / ((1 - x)^2*(1 + x)*(1 + x^2)^2) + O(x^40)) \\ Colin Barker, Aug 15 2019

For k > 2:
  a(4*k)   = 4*k+1,
  a(4*k+1) = 4*k-2,
  a(4*k+2) = 4,
  a(4*k+3) = 3.
From Colin Barker, Aug 04 2019: (Start)
G.f.: x*(1 + 3*x^2 + 2*x^3 - 2*x^4 + 4*x^5 - 7*x^6 + 6*x^7 - 3*x^8) / ((1 - x)^2*(1 + x)*(1 + x^2)^2).
a(n) = a(n-1) - a(n-2) + a(n-3) + a(n-4) - a(n-5) + a(n-6) - a(n-7) for n > 9.
(End)

A275153 A linear-recurrent solution to Hofstadter's Q-recurrence.

Original entry on oeis.org

9, 0, 0, 0, 7, 9, 9, 10, 4, 9, 9, 3, 9, 16, 9, 9, 20, 4, 9, 18, 3, 9, 34, 9, 9, 40, 4, 9, 27, 3, 9, 61, 9, 9, 80, 4, 9, 36, 3, 9, 97, 9, 9, 160, 4, 9, 45, 3, 9, 142, 9, 9, 320, 4, 9, 54, 3, 9, 196, 9, 9, 640, 4, 9, 63, 3, 9, 259, 9, 9, 1280, 4, 9, 72, 3, 9, 331, 9, 9, 2560

Offset: 1

Nathan Fox, Jul 17 2016

nonn

a(n) is the solution to the recurrence relation a(n) = a(n-a(n-1)) + a(n-a(n-2)) [Hofstadter's Q recurrence], with the initial conditions: a(n) = 0 if n <= 0; a(1) = 9, a(2) = 0, a(3) = 0, a(4) = 0, a(5) = 7, a(6) = 9, a(7) = 9, a(8) = 10, a(9) = 4, a(10) = 9, a(11) = 9, a(12) = 3.

This sequence is an interleaving of nine simpler sequences. Six are eventually constant, one is a linear polynomial, one is a quadratic polynomial, and one is a geometric sequence.

Nathan Fox, Table of n, a(n) for n = 1..1000
Nathan Fox, Finding Linear-Recurrent Solutions to Hofstadter-Like Recurrences Using Symbolic Computation, arXiv:1609.06342 [math.NT], 2016.
Index entries for linear recurrences with constant coefficients, signature (0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, -9, 0, 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, 0, 0, -2).

Cf. A005185, A188670, A244477, A264756, A264757, A264758, A268368.

Join[{9, 0, 0, 0}, LinearRecurrence[{0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, -9, 0, 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, 0, 0, -2}, {7, 9, 9, 10, 4, 9, 9, 3, 9, 16, 9, 9, 20, 4, 9, 18, 3, 9, 34, 9, 9, 40, 4, 9, 27, 3, 9, 61, 9, 9, 80, 4, 9, 36, 3, 9}, 100]] (* Jean-François Alcover, Dec 01 2018 *)

a(3) = 0, a(4) = 0; otherwise:
a(9n) = 4,     a(9n+1) = 9         a(9n+2) = 9n      a(9n+3) = 3.
a(9n+4) = 9,   a(9n+5) = (9*n^2 + 9*n + 14)/2,     a(9n+6) = 9.
a(9n+7) = 9,   a(9n+8) = 10*2^n.
a(n) = 5*a(n-9) - 9*a(n-18) + 7*a(n-27) - 2*a(n-36) for n>40.
G.f.: -(18*x^39 +6*x^38 +8*x^35 +10*x^34 +18*x^33 +18*x^32 +14*x^31 -45*x^30 -15*x^29 -18*x^28 +18*x^27 -20*x^26 -30*x^25 -45*x^24 -45*x^23 -17*x^22 +36*x^21 +12*x^20 +27*x^19 -45*x^18 +16*x^17 +30*x^16 +36*x^15 +36*x^14 +19*x^13 -9*x^12 -3*x^11 -9*x^10 +36*x^9 -4*x^8 -10*x^7 -9*x^6 -9*x^5 -7*x^4 -9)/((2*x^9-1)*(x-1)^3*(x^2+x+1)^3*(x^6+x^3+1)^3).

A284644 a(1) = a(2) = 2, a(3) = 1; a(n) = a(n-a(n-1)) + a(n-a(n-2)) for n > 3.

Original entry on oeis.org

2, 2, 1, 3, 5, 3, 5, 6, 4, 6, 10, 5, 7, 9, 9, 10, 11, 11, 12, 10, 14, 11, 9, 16, 14, 11, 17, 21, 11, 16, 19, 17, 19, 20, 19, 21, 21, 22, 22, 22, 24, 21, 23, 23, 22, 25, 25, 18, 35, 26, 24, 32, 25, 22, 35, 34, 20, 38, 36, 27, 34, 40, 20, 39, 33, 36, 39, 28, 40, 37, 39

Offset: 1

Altug Alkan, Mar 31 2017

A "brother" to Hofstadter's Q-sequence (A005185) and A244477 using with different starting values.

			a(4) = 3 because a(4) = a(4 - a(3)) + a(4 - a(2)) = a(3) + a(2) = 3.

Altug Alkan, Table of n, a(n) for n = 1..10000
Altug Alkan, Alternative scatterplot of A284644
Altug Alkan, On a Generalization of Hofstadter's Q-Sequence: A Family of Chaotic Generational Structures, Complexity (2018) Article ID 8517125.
Altug Alkan, Nathan Fox, and Orhan Ozgur Aybar, On Hofstadter Heart Sequences, Complexity, 2017, 2614163.

Cf. A005185, A244477.

A284644:= proc(n) option remember; procname(n-procname(n-1)) +procname(n-procname(n-2)) end proc:
A284644(1):= 2: A284644(2):= 2: A284644(3):= 1:
map(A284644, [$1..1000]);

a[1] = a[2] = 2; a[3] = 1; a[n_] := a[n] = a[n - a[n - 1]] + a[n - a[n - 2]]; Table[a@ n, {n, 72}] (* Michael De Vlieger, Apr 02 2017 *)

a=vector(1000); a[1]=a[2]=2; a[3]=1; for(n=4, #a, a[n] = a[n-a[n-1]]+a[n-a[n-2]]); a

A309494 a(1) = a(2) = a(3) = a(5) = 1, a(4) = 2; a(n) = a(n-a(n-3)) + a(n-a(n-4)) for n > 5.

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 3, 5, 8, 8, 7, 5, 2, 5, 13, 12, 18, 3, 5, 6, 4, 23, 21, 9, 5, 2, 5, 26, 14, 31, 3, 5, 6, 4, 36, 34, 9, 5, 2, 5, 39, 14, 44, 3, 5, 6, 4, 49, 47, 9, 5, 2, 5, 52, 14, 57, 3, 5, 6, 4, 62, 60, 9, 5, 2, 5, 65, 14, 70, 3, 5, 6, 4, 75, 73, 9, 5, 2, 5, 78, 14, 83, 3, 5, 6, 4, 88, 86, 9, 5, 2, 5, 91

Offset: 1

Altug Alkan, Aug 04 2019

A well-defined solution sequence for recurrence a(n) = a(n-a(n-3)) + a(n-a(n-4)).

Robert Israel, Table of n, a(n) for n = 1..10000
Index entries for linear recurrences with constant coefficients, signature (0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,-1).

Cf. A064657, A244477, A309492.

for n from 1 to 5 do a[n]:= `if`(n=4,2,1) od:
for n from 6 to 100 do a[n]:= a[n-a[n-3]] + a[n-a[n-4]] od:
seq(a[n],n=1..100); # Robert Israel, Aug 07 2019

a[1]=a[2]=a[3]=a[5]=1; a[4]=2; a[n_] := a[n] = a[n - a[n-3]] + a[n - a[n-4]]; Array[a, 93] (* Giovanni Resta, Aug 07 2019 *)

q=vector(100); q[1]=q[2]=q[3]=q[5]=1; q[4]=2; for(n=6, #q, q[n]=q[n-q[n-3]]+q[n-q[n-4]]); q

Vec(x*(1 + x + x^2 + 2*x^3 + x^4 + 2*x^5 + 3*x^6 + 5*x^7 + 8*x^8 + 8*x^9 + 7*x^10 + 5*x^11 + 2*x^12 + 3*x^13 + 11*x^14 + 10*x^15 + 14*x^16 + x^17 + x^18 - 6*x^20 + 7*x^21 + 5*x^22 - 5*x^23 - 5*x^24 - 2*x^25 - 4*x^26 + x^27 - 9*x^28 - 3*x^29 - 2*x^30 - 3*x^31 - 3*x^32 + x^33 - 2*x^34 - 2*x^36 - 2*x^41) / ((1 - x)^2*(1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9 + x^10 + x^11 + x^12)^2) + O(x^80)) \\ Colin Barker, Aug 08 2019

For k > 1,
  a(13*k-9) = 13*k-8,
  a(13*k-8) = 3,
  a(13*k-7) = 5,
  a(13*k-6) = 6,
  a(13*k-5) = 4,
  a(13*k-4) = 13*k-3,
  a(13*k-3) = 13*k-5,
  a(13*k-2) = 9,
  a(13*k-1) = 5,
  a(13*k)   = 2,
  a(13*k+1) = 5,
  a(13*k+2) = 13*k,
  a(13*k+3) = 14.
From Colin Barker, Aug 05 2019: (Start)
G.f.: x*(1 + x + x^2 + 2*x^3 + x^4 + 2*x^5 + 3*x^6 + 5*x^7 + 8*x^8 + 8*x^9 + 7*x^10 + 5*x^11 + 2*x^12 + 3*x^13 + 11*x^14 + 10*x^15 + 14*x^16 + x^17 + x^18 - 6*x^20 + 7*x^21 + 5*x^22 - 5*x^23 - 5*x^24 - 2*x^25 - 4*x^26 + x^27 - 9*x^28 - 3*x^29 - 2*x^30 - 3*x^31 - 3*x^32 + x^33 - 2*x^34 - 2*x^36 - 2*x^41) / ((1 - x)^2*(1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9 + x^10 + x^11 + x^12)^2).
a(n) = 2*a(n-13) - a(n-26) for n > 42.
(End)

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

C

Haskell

Magma

Maple

Mathematica

MuPAD

PARI

Python

Sage

Scheme

Scheme

A264756 An eventually quasilinear solution to Hofstadter's Q recurrence.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A264757 An eventually quasi-quadratic solution to Hofstadter's Q recurrence.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A264758 An eventually quasi-cubic solution to Hofstadter's Q recurrence.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A268368 An eventually quasi-quadratic sequence satisfying a Hofstadter-like recurrence.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A296518 a(1) = 3, a(2) = a(5) = 1, a(3) = a(4) = a(6) = 2; a(n) = a(n-a(n-1)) + a(n-a(n-2)) + a(n-a(n-3)) for n > 6.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Scheme

Formula