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

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

Author

Nathan Fox, Jul 17 2016

Keywords

• nonn

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

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

Crossrefs

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

Programs

Mathematica

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

Formula

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