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

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

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

Links

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

Formula

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

Mathematica

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

Crossrefs

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

Sequence in context: A049475 A264084 A080271 * A274686 A217397 A104292

Adjacent sequences: A275358 A275359 A275360 * A275362 A275363 A275364

Keyword

sign

Author

Nathan Fox, Jul 24 2016

Status

approved