

A264757


An eventually quasiquadratic solution to Hofstadter's Q recurrence.


8



4, 0, 5, 6, 2, 6, 6, 3, 11, 6, 2, 12, 6, 3, 23, 6, 2, 18, 6, 3, 41, 6, 2, 24, 6, 3, 65, 6, 2, 30, 6, 3, 95, 6, 2, 36, 6, 3, 131, 6, 2, 42, 6, 3, 173, 6, 2, 48, 6, 3, 221, 6, 2, 54, 6, 3, 275, 6, 2, 60, 6, 3, 335, 6, 2, 66, 6, 3, 401, 6, 2, 72, 6, 3, 473, 6
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


COMMENTS

a(n) is the solution to the recurrence relation a(n) = a(na(n1)) + a(na(n2)) [Hofstadter's Q recurrence], with the initial conditions: a(n) = 0 if n <= 0; a(1) = 4, a(2) = 0, a(3) = 5, a(4) = 6, a(5) = 2, a(6) = 6, a(7) = 6, a(8) = 3.


LINKS

Colin Barker, Table of n, a(n) for n = 1..1000
Nathan Fox, Quasipolynomial Solutions to the Hofstadter QRecurrence, arXiv preprint arXiv:1511.06484 [math.NT], 2015.
Index entries for linear recurrences with constant coefficients, signature (0,0,0,0,0,3,0,0,0,0,0,3,0,0,0,0,0,1).


FORMULA

a(1) = 4, a(2) = 0; thereafter a(6*n) = 6*n, a(6*n+1) = 6, a(6*n+2) = 3, a(6*n+3) = 3*n^2+3*n+5, a(6*n+4) = 6, a(6*n+5) = 2.
From Colin Barker, Nov 14 2016: (Start)
G.f.: x*(4 + 5*x^2 + 6*x^3 + 2*x^4 + 6*x^5  6*x^6 + 3*x^7  4*x^8  12*x^9  4*x^10  6*x^11  6*x^13 + 5*x^14 + 6*x^15 + 2*x^16 + 2*x^18 + 3*x^19) / ((1  x)^3 * (1 + x)^3 * (1  x + x^2)^3 * (1 + x + x^2)^3).
a(n) = 3*a(n6)  3*a(n12) + a(n18) for n>20.
(End)


MATHEMATICA

Table[If[n < 3, #  n  1, #] &@ Switch[Mod[n, 6], 0, n, 1, 6, 2, 3, 3, 3 #^2 + 3 # + 5 &[(n  3)/6], 4, 6, 5, 2], {n, 75}] (* or *)
Rest@ CoefficientList[Series[x (4 + 5 x^2 + 6 x^3 + 2 x^4 + 6 x^5  6 x^6 + 3 x^7  4 x^8  12 x^9  4 x^10  6 x^11  6 x^13 + 5 x^14 + 6 x^15 + 2 x^16 + 2 x^18 + 3 x^19)/((1  x)^3*(1 + x)^3*(1  x + x^2)^3*(1 + x + x^2)^3), {x, 0, 76}], x] (* Michael De Vlieger, Nov 14 2016 *)


PROG

(PARI) Vec(x*(4+5*x^2+6*x^3+2*x^4+6*x^56*x^6+3*x^74*x^812*x^94*x^106*x^116*x^13+5*x^14+6*x^15+2*x^16+2*x^18+3*x^19)/((1x)^3*(1+x)^3*(1x+x^2)^3*(1+x+x^2)^3) + O(x^100)) \\ Colin Barker, Nov 14 2016


CROSSREFS

Cf. A005185, A188670, A244477, A264756, A264758.
Sequence in context: A335775 A308108 A320374 * A195773 A153018 A102913
Adjacent sequences: A264754 A264755 A264756 * A264758 A264759 A264760


KEYWORD

nonn,easy


AUTHOR

Nathan Fox, Nov 23 2015


STATUS

approved



