|
|
A269328
|
|
An eventually quasilinear solution to Hofstadter's Q recurrence.
|
|
3
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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) = 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
|
|
LINKS
|
Index entries for linear recurrences with constant coefficients, signature (0, 0, 0, 0, 2, 0, 0, 0, 0, -1).
|
|
FORMULA
|
a(4) = 3; otherwise a(5n) = 6n, a(5n+1) = 5, a(5n+2) = 2, a(5n+3) = 5n, a(5n+4) = 5.
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)
|
|
EXAMPLE
|
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)
|
|
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 *)
|
|
PROG
|
(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
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|