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

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,3

Comments

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.

Links

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

Formula

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

Mathematica

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

Prog

(PARI) 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
(Magma) [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

Crossrefs

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

Sequence in context: A293521 A285443 A110898 * A267942 A147994 A106365

Adjacent sequences: A264753 A264754 A264755 * A264757 A264758 A264759

Keyword

nonn,easy

Author

Nathan Fox, Nov 23 2015

Status

approved