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

5, 2, 0, 3, 6, 5, 2, 5, 5, 12, 5, 2, 10, 5, 18, 5, 2, 15, 5, 24, 5, 2, 20, 5, 30, 5, 2, 25, 5, 36, 5, 2, 30, 5, 42, 5, 2, 35, 5, 48, 5, 2, 40, 5, 54, 5, 2, 45, 5, 60, 5, 2, 50, 5, 66, 5, 2, 55, 5, 72, 5, 2, 60, 5, 78, 5, 2, 65, 5, 84, 5, 2, 70, 5, 90

Offset: 1

Author

Nathan Fox, Feb 23 2016

Keywords

• nonn
• tabf

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) = 5, a(2) = 2, a(3) = 0, a(4) = 3, a(5) = 6, a(6) = 5, a(7) = 2.

Starting from n=5, this sequence consists of five interleaved linear sequences with three different slopes.

Square array read by rows: T(j,k), j>=1, 1<=k<=5, in which row j list [5, 2, 5*(j-1), 5, 6*j], except T(1,4) = 3, not 5. - Omar E. Pol, Jun 22 2016

Examples

			From _Omar E. Pol_, Jun 22 2016: (Start)
Written as a square array T(j,k) with five columns the sequence begins:
5, 2,  0, 3,  6;
5, 2,  5, 5, 12;
5, 2, 10, 5, 18;
5, 2, 15, 5, 24;
5, 2, 20, 5, 30;
5, 2, 25, 5, 36;
5, 2, 30, 5, 42;
5, 2, 35, 5, 48;
5, 2, 40, 5, 54;
5, 2, 45, 5, 60;
5, 2, 50, 5, 66;
5, 2, 55, 5, 72;
5, 2, 60, 5, 78;
5, 2, 65, 5, 84;
5, 2, 70, 5, 90;
...
Note that T(1,4) = 3, not 5. (End)
		

Links

• Vincenzo Librandi, Table of n, a(n) for n = 1..10000
• 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, 2, 0, 0, 0, 0, -1).

Crossrefs

Cf. A005185, A188670, A244477, A264756.

Programs

Magma

I:=[5,2,0,3,6,5,2,5,5,12,5,2,10,5]; [n le 14 select I[n] else 2*Self(n-5)-Self(n-10): n in [1..100]]; // Vincenzo Librandi, Dec 16 2018

Mathematica

Join[{5, 2, 0, 3}, LinearRecurrence[{0, 0, 0, 0, 2, 0, 0, 0, 0, -1} , {6, 5, 2, 5, 5, 12, 5, 2, 10, 5}, 80]] (* Jean-François Alcover, Dec 16 2018 *)
CoefficientList[Series[(-2 x^13 - x^8 + 5 x^7 - 2 x^6 - 5 x^5 + 6 x^4 + 3 x^3 + 2 x + 5) / (x^10 - 2 x^5 + 1), {x, 0, 100}], x] (* Vincenzo Librandi, Dec 16 2018 *)

Formula

a(4) = 3; otherwise a(5n) = 6n, a(5n+1) = 5, a(5n+2) = 2, a(5n+3) = 5n, a(5n+4) = 5.

From Chai Wah Wu, Jun 22 2016: (Start)

a(n) = 2*a(n-5) - a(n-10) for n > 14.

G.f.: x*(-2*x^13 - x^8 + 5*x^7 - 2*x^6 - 5*x^5 + 6*x^4 + 3*x^3 + 2*x + 5)/(x^10 - 2*x^5 + 1). (End)