A264757 - OEIS

%I #16 Nov 14 2016 09:04:17

%S 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,

%T 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,

%U 2,60,6,3,335,6,2,66,6,3,401,6,2,72,6,3,473,6

%N An eventually quasi-quadratic solution to Hofstadter's Q recurrence.

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

%H Colin Barker, <a href="/A264757/b264757.txt">Table of n, a(n) for n = 1..1000</a>

%H Nathan Fox, <a href="http://arxiv.org/abs/1511.06484">Quasipolynomial Solutions to the Hofstadter Q-Recurrence</a>, arXiv preprint arXiv:1511.06484 [math.NT], 2015.

%H <a href="/index/Rec#order_18">Index entries for linear recurrences with constant coefficients</a>, signature (0,0,0,0,0,3,0,0,0,0,0,-3,0,0,0,0,0,1).

%F 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.

%F From _Colin Barker_, Nov 14 2016: (Start)

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

%F a(n) = 3*a(n-6) - 3*a(n-12) + a(n-18) for n>20.

%F (End)

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

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

%o (PARI) Vec(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) + O(x^100)) \\ _Colin Barker_, Nov 14 2016

%Y Cf. A005185, A188670, A244477, A264756, A264758.

%K nonn,easy

%O 1,1

%A _Nathan Fox_, Nov 23 2015