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

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

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

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.

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

Formula

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)

Mathematica

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

Prog

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

Crossrefs

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

Sequence in context: A198114 A293384 A193012 * A362149 A195484 A130203

Adjacent sequences: A264755 A264756 A264757 * A264759 A264760 A264761

Keyword

nonn,easy

Author

Nathan Fox, Nov 23 2015

Status

approved