A264756 An eventually quasilinear solution to Hofstadter's Q recurrence.
1, 0, 3, 3, 2, 6, 3, 2, 9, 3, 2, 12, 3, 2, 15, 3, 2, 18, 3, 2, 21, 3, 2, 24, 3, 2, 27, 3, 2, 30, 3, 2, 33, 3, 2, 36, 3, 2, 39, 3, 2, 42, 3, 2, 45, 3, 2, 48, 3, 2, 51, 3, 2, 54, 3, 2, 57, 3, 2, 60, 3, 2, 63, 3, 2, 66, 3, 2, 69, 3, 2, 72, 3, 2, 75, 3, 2, 78, 3, 2, 81
Offset: 1
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.
- 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,2,0,0,-1).
Programs
-
Magma
[1,0] cat [2+(n-3)*(1+Floor(-n/3)+Floor(n/3))-Floor(-(n+1)/3)-Floor((n+1)/3): n in [3..100]]; // Vincenzo Librandi, Nov 25 2015
-
Mathematica
CoefficientList[Series[-(2*x^7 + 2*x^6 - 2*x^4 - x^3 - 3*x^2 - 1)/((x - 1)^2*(x^2 + x + 1)^2), {x, 0, 100}], x] (* Wesley Ivan Hurt, Nov 24 2015 *) Join[{1, 0}, LinearRecurrence[{0, 0, 2, 0, 0, -1}, {3, 3, 2, 6, 3, 2}, 100]] (* Vincenzo Librandi, Nov 25 2015 *) -
PARI
Vec(-x*(2*x^7+2*x^6-2*x^4-x^3-3*x^2-1)/((x-1)^2*(x^2+x+1)^2) + O(x^100)) \\ Colin Barker, Nov 23 2015
Formula
a(1) = 1, a(2) = 0; thereafter a(3n) = 3n, a(3n+1) = 3, a(3n+2) = 2.
From Colin Barker, Nov 23 2015: (Start)
a(n) = 2*a(n-3) - a(n-6) for n>8.
G.f.: -x*(2*x^7+2*x^6-2*x^4-x^3-3*x^2-1) / ((x-1)^2*(x^2+x+1)^2).
(End)
a(1) = 1, a(2) = 0, a(n) = 2 + (n-3)*(1 + floor(-n/3) + floor(n/3)) - floor(-(n+1)/3) - floor((n+1)/3) for n>2. - Wesley Ivan Hurt, Nov 24 2015
Comments