login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

A quasi-periodic solution to Hofstadter's Q recurrence.
16

%I #27 Nov 23 2015 14:47:45

%S 3,6,5,3,6,8,3,6,13,3,6,21,3,6,34,3,6,55,3,6,89,3,6,144,3,6,233,3,6,

%T 377,3,6,610,3,6,987,3,6,1597,3,6,2584,3,6,4181,3,6,6765,3,6,10946,3,

%U 6,17711,3,6,28657,3,6,46368,3,6,75025,3,6,121393

%N A quasi-periodic 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(n) = 3 if n = 0,3; a(n) = 6 if n = 1,4; a(2) = 5; a(5) = 8.

%D F. Ruskey, Fibonacci meets Hofstadter, Fibonacci Quart. 49 (2011), no. 3, 227-230.

%H Colin Barker, <a href="/A188670/b188670.txt">Table of n, a(n) for n = 0..1000</a>

%H Nathan Fox, <a href="https://vimeo.com/141111990">Linear-Recurrent Solutions to Meta-Fibonacci Recurrences, Part 1 (video)</a>, Rutgers Experimental Math Seminar, Oct 01 2015. Part 2 is vimeo.com/141111991.

%H F. Ruskey <a href="http://webhome.cs.uvic.ca/~ruskey/Publications/MetaFib/FiboHofs.html">Fibonacci meets Hofstadter</a>

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

%F a(3n) = 3, a(3n+1) = 6, a(3n+2) = Fibonacci(n+5).

%F From _Colin Barker_, Nov 23 2015: (Start)

%F a(n) = 2*a(n-3)-a(n-9) for n>8.

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

%F (End)

%o (PARI)

%o A188670(n)=

%o {

%o local(m=n%3);

%o if (m==0,return(3));

%o if (m==1,return(6));

%o return(fibonacci(n\3+5));

%o }

%o vector(66,n,A188670(n-1)) /* show terms */ /* _Joerg Arndt_, Apr 08 2011 */

%o (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

%Y Cf. A005185 with different initial conditions.

%K nonn,easy

%O 0,1

%A _Frank Ruskey_, Apr 08 2011