cp's OEIS Frontend

A283879 An eventually quasilinear solution to Hofstadter's Q recurrence.

%I A283879 #10 May 25 2025 12:05:40
%S A283879 4,1,0,3,3,1,4,8,7,1,4,12,11,1,4,16,15,1,4,20,19,1,4,24,23,1,4,28,27,
%T A283879 1,4,32,31,1,4,36,35,1,4,40,39,1,4,44,43,1,4,48,47,1,4,52,51,1,4,56,
%U A283879 55,1,4,60,59,1,4,64,63,1,4,68,67,1,4,72,71,1,4
%N A283879 An eventually quasilinear solution to Hofstadter's Q recurrence.
%C A283879 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) = 1, a(3) = 0, a(4) = 3, a(5) = 3, a(6) = 1, a(7) = 4, a(8) = 8.
%H A283879 Nathan Fox, <a href="/A283879/b283879.txt">Table of n, a(n) for n = 1..10000</a>
%H A283879 <a href="/index/Rec#order_07">Index entries for linear recurrences with constant coefficients</a>, signature (1, -1, 1, 1, -1, 1, -1).
%F A283879 a(1) = 4, a(4) = 3; otherwise a(4n) = 4n, a(4n+1) = 4n-1, a(4n+2) = 1, a(4n+3) = 4.
%F A283879 G.f.: (-x^10-3*x^9+3*x^8+2*x^7+4*x^5-5*x^4+3*x^2-3*x+4) / ((1+x)*(-1+x)^2*(1+x^2)^2).
%F A283879 a(n) = a(n-1) - a(n-2) + a(n-3) + a(n-4) - a(n-5) + a(n-6) - a(n-7) for n > 11.
%p A283879 A283879:=proc(n) option remember: if n <= 0 then 0: elif n = 1 then 4: elif n = 2 then 1: elif n = 3 then 0: elif n = 4 then 3: elif n = 5 then 3: elif n = 6 then 1: elif n = 7 then 4: elif n = 8 then 8: else A283879(n-A283879(n-1)) + A283879(n-A283879(n-2)): fi: end:
%t A283879 LinearRecurrence[{1,-1,1,1,-1,1,-1},{4,1,0,3,3,1,4,8,7,1,4},80] (* _Harvey P. Dale_, May 25 2025 *)
%Y A283879 Cf. A005185, A188670, A244477, A264756, A283878.
%K A283879 nonn
%O A283879 1,1
%A A283879 _Nathan Fox_, Mar 19 2017