OFFSET
0,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(n) = 3 if n = 0,3; a(n) = 6 if n = 1,4; a(2) = 5; a(5) = 8.
REFERENCES
F. Ruskey, Fibonacci meets Hofstadter, Fibonacci Quart. 49 (2011), no. 3, 227-230.
LINKS
Colin Barker, Table of n, a(n) for n = 0..1000
Nathan Fox, Linear-Recurrent Solutions to Meta-Fibonacci Recurrences, Part 1 (video), Rutgers Experimental Math Seminar, Oct 01 2015. Part 2 is vimeo.com/141111991.
F. Ruskey Fibonacci meets Hofstadter
Index entries for linear recurrences with constant coefficients, signature (0,0,2,0,0,0,0,0,-1).
FORMULA
a(3n) = 3, a(3n+1) = 6, a(3n+2) = Fibonacci(n+5).
From Colin Barker, Nov 23 2015: (Start)
a(n) = 2*a(n-3)-a(n-9) for n>8.
G.f.: -(3*x^8+6*x^7+3*x^6+2*x^5+6*x^4+3*x^3-5*x^2-6*x-3) / ((x-1)*(x^2+x+1)*(x^6+x^3-1)).
(End)
PROG
(PARI)
A188670(n)=
{
local(m=n%3);
if (m==0, return(3));
if (m==1, return(6));
return(fibonacci(n\3+5));
}
vector(66, n, A188670(n-1)) /* show terms */ /* Joerg Arndt, Apr 08 2011 */
(PARI) Vec(-(3*x^8+6*x^7+3*x^6+2*x^5+6*x^4+3*x^3-5*x^2-6*x-3)/((x-1)*(x^2+x+1)*(x^6+x^3-1)) + O(x^100)) \\ Colin Barker, Nov 23 2015
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Frank Ruskey, Apr 08 2011
STATUS
approved