A268368 -id:A268368 - cp's OEIS frontend

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.

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)

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).

A275361 An eventually quasilinear solution to Hofstadter's Q-recurrence.

Original entry on oeis.org

0, 4, -40, -9, 8, -8, 7, 1, 5, 13, -24, -1, 8, 8, 8, 1, 5, 13, -8, 7, 8, 8, 23, 1, 5, 13, 8, 15, 8, 16, 31, 1, 5, 13, 24, 23, 8, 24, 39, 1, 5, 13, 40, 31, 8, 32, 47, 1, 5, 13, 56, 39, 8, 40, 55, 1, 5, 13, 72, 47, 8, 48, 63, 1, 5, 13, 88, 55, 8, 56, 71

Offset: 1

Nathan Fox, Jul 24 2016

sign

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 first 45 terms as initial conditions.

This is a quasilinear sequence with quasiperiod 8. Four of the component sequences are constant, three have slope 1, and one has slope 2.

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, 2, 0, 0, 0, 0, 0, 0, 0, -1).

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

Join[{0, 4, -40, -9, 8, -8, 7, 1, 5, 13, -24, -1, 8, 8, 8}, LinearRecurrence[ {0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, -1}, {1, 5, 13, -8, 7, 8, 8, 23, 1, 5, 13, 8, 15, 8, 16, 31}, 100]] (* Jean-François Alcover, Dec 12 2018 *)

a(1) = 0, a(2) = 4, a(14) = 8, a(15) = 8; otherwise:
a(8n) = 1, a(8n+1) = 5, a(8n+2) = 13, a(8n+3) = 16n-40, a(8n+4) = 8n-9, a(8n+5) = 8, a(8n+6) = 8n-8, a(8n+7) = 8n+7.
a(n) = 2*a(n-8) - a(n-16) for n>31.
G.f.: -(7*x^30 -8*x^29 -14*x^22 +16*x^21 +9*x^17 +5*x^16 +x^15 +6*x^14 -24*x^13 +8*x^12 -17*x^11 -56*x^10 -5*x^9 -5*x^8 -x^7 -7*x^6 +8*x^5 -8*x^4 +9*x^3 +40*x^2 -4*x)/((x-1)^2*(x+1)^2*(x^2+1)^2*(x^4+1)^2).

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

Original entry on oeis.org

-9, 2, 9, 2, 0, 7, 9, 10, 3, 0, 2, 9, 2, 9, 9, 9, 20, 3, 9, 22, 9, 2, 18, 9, 18, 30, 3, 18, 32, 9, 2, 27, 9, 27, 40, 3, 27, 42, 9, 2, 36, 9, 36, 50, 3, 36, 52, 9, 2, 45, 9, 45, 60, 3, 45, 62, 9, 2, 54, 9, 54, 70, 3, 54, 72, 9, 2, 63, 9, 63, 80, 3, 63, 82

Offset: 1

Nathan Fox, Jul 24 2016

sign

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) = 2, a(3) = 9, a(4) = 2, a(5) = 0, a(6) = 7, a(7) = 9, a(8) = 10, a(9) = 3, a(10) = 0, a(11) = 2, a(12) = 9, a(13) = 2, a(14) = 9, a(15) = 9, a(16) = 9.

This is a quasilinear sequence with quasiperiod 9. Four of the component sequences are constant, three have slope 1, and two have slope 10/9.

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, 2, 0, 0, 0, 0, 0, 0, 0, 0, -1).

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

Join[{-9, 2, 9, 2, 0, 7, 9, 10, 3, 0, 2}, LinearRecurrence[{0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, -1}, {9, 2, 9, 9, 9, 20, 3, 9, 22, 9, 2, 18, 9, 18, 30, 3, 18, 32}, 100]] (* Jean-François Alcover, Dec 13 2018 *)

a(6) = 7, a(7) = 9, a(11) = 2; otherwise:
a(9n) = 3, a(9n+1) = 9n-9, a(9n+2) = 10n+2, a(9n+3) = 9, a(9n+4) = 2, a(9n+5) = 9n, a(9n+6) = 9, a(9n+7) = 9n, a(9n+8) = 10n+10.
a(n) = 2*a(n-9) - a(n-18) for n>29.
G.f.: -(10*x^28 -9*x^24 +2*x^23 -20*x^19 +3*x^17 +9*x^15 +5*x^14 -9*x^13 +2*x^12 +9*x^11 +2*x^10 -18*x^9 -3*x^8 -10*x^7 -9*x^6 -7*x^5 -2*x^3 -9*x^2 -2*x+9)/((x-1)^2*(x^2+x+1)^2*(x^6+x^3+1)^2).

A296786 a(1) = a(2) = a(5) = 2, a(3) = 1, a(4) = 3, a(6) = 5; 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

2, 2, 1, 3, 2, 5, 7, 8, 7, 4, 11, 12, 11, 4, 15, 16, 15, 4, 19, 20, 19, 4, 23, 24, 23, 4, 27, 28, 27, 4, 31, 32, 31, 4, 35, 36, 35, 4, 39, 40, 39, 4, 43, 44, 43, 4, 47, 48, 47, 4, 51, 52, 51, 4, 55, 56, 55, 4, 59, 60, 59, 4, 63, 64, 63, 4, 67, 68, 67, 4, 71, 72, 71, 4, 75, 76, 75, 4, 79, 80, 79, 4

Offset: 1

Altug Alkan, Dec 20 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)). See comments in A296518.

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.
Index entries for linear recurrences with constant coefficients, signature (0,0,0,2,0,0,0,-1).

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

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

a[n_] := a[n] = If[n<7, {2, 2, 1, 3, 2, 5}[[n]], a[n - a[n-1]] + a[n - a[n-2]] + a[n - a[n-3]]]; Array[a, 100] (* after Giovanni Resta at A296440 *)

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

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

a(4*k-1) = a(4*k+1) = 4*k-1, a(4*k) = 4*k, a(4*k+2) = 4, for k > 1.
From Colin Barker, Dec 28 2017: (Start)
G.f.: x*(2 + 2*x + x^2 + 3*x^3 - 2*x^4 + x^5 + 5*x^6 + 2*x^7 + 5*x^8 - 4*x^9 - 2*x^10 - x^11 - x^12 + 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)

A275365 a(1)=2, a(2)=2; thereafter a(n) = a(n-a(n-1)) + a(n-a(n-2)).

Original entry on oeis.org

0, 2, 2, 4, 2, 6, 2, 8, 2, 10, 2, 12, 2, 14, 2, 16, 2, 18, 2, 20, 2, 22, 2, 24, 2, 26, 2, 28, 2, 30, 2, 32, 2, 34, 2, 36, 2, 38, 2, 40, 2, 42, 2, 44, 2, 46, 2, 48, 2, 50, 2, 52, 2, 54, 2, 56, 2, 58, 2, 60, 2, 62, 2, 64, 2, 66, 2, 68, 2, 70, 2, 72, 2, 74

Offset: 0

Nathan Fox, Jul 24 2016

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) = 2, a(2) = 2.
Starting with n=1, a(n) is A005843 interleaved with A007395.
This sequence is the same as A133265 with the leading 2 changed to a 0.

Nathan Fox, Table of n, a(n) for n = 0..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,2,0,-1).

Cf. A005185, A133265, A188670, A244477, A264756, A264757, A264758, A268368, A275153, A275361, A275362.

Join[{0}, LinearRecurrence[{0, 2, 0, -1}, {2, 2, 4, 2}, 73]] (* Jean-François Alcover, Feb 19 2019 *)

a(0) = 0; thereafter, a(2n) = 2, a(2n+1) = 2n+2.
a(n) = 2*a(n-2) - a(n-4) for n>4.
G.f.: -(2*x^3 -2*x -2)/((x-1)^2*(x+1)^2).

cp's OEIS Frontend

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

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A275361 An eventually quasilinear solution to Hofstadter's Q-recurrence.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A296786 a(1) = a(2) = a(5) = 2, a(3) = 1, a(4) = 3, a(6) = 5; 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

Formula

A275365 a(1)=2, a(2)=2; thereafter a(n) = a(n-a(n-1)) + a(n-a(n-2)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula