cp's OEIS Frontend

A283881 A linear-recurrent solution to Hofstadter's Q recurrence.

%I A283881 #10 Mar 08 2024 12:14:10
%S A283881 7,0,8,7,7,8,4,7,7,16,7,7,16,4,7,14,24,7,7,32,4,7,21,32,7,7,64,4,7,28,
%T A283881 40,7,7,128,4,7,35,48,7,7,256,4,7,42,56,7,7,512,4,7,49,64,7,7,1024,4,
%U A283881 7,56,72,7,7,2048,4,7,63,80,7,7,4096,4,7,70,88,7,7
%N A283881 A linear-recurrent solution to Hofstadter's Q recurrence.
%C A283881 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) = 7, a(2) = 0, a(3) = 8, a(4) = 7, a(5) = 7, a(6) = 8, a(7) = 4.
%C A283881 This sequence is an interleaving of seven simpler sequences. Four are constant, two are linear polynomials, and one is a geometric sequence.
%H A283881 Nathan Fox, <a href="/A283881/b283881.txt">Table of n, a(n) for n = 1..10000</a>
%H A283881 <a href="/index/Rec#order_21">Index entries for linear recurrences with constant coefficients</a>, signature (0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, -5, 0, 0, 0, 0, 0, 0, 2).
%F A283881 a(7n) = 4, a(7n+1) = 7, a(7n+2) = 7n, a(7n+3) = 8n+8, a(7n+4) = 7, a(7n+5) = 7, a(7n+6) = 2^(n+3).
%F A283881 G.f.: (-8*x^20-8*x^19-14*x^18-14*x^17+14*x^15-14*x^14+12*x^13 +16*x^12 +21*x^11 +21*x^10+16*x^9-7*x^8+21*x^7-4*x^6-8*x^5-7*x^4-7*x^3 -8*x^2-7) / ((-1+2*x^7)*(-1+x)^2*(1+x+x^2+x^3+x^4+x^5+x^6)^2).
%F A283881 a(n) = 4*a(n-7) - 5*a(n-14) + 2*a(n-21) for n > 21.
%p A283881 A283881:=proc(n) option remember: if n <= 0 then 0: elif n = 1 then 7: elif n = 2 then 0: elif n = 3 then 8: elif n = 4 then 7: elif n = 5 then 7: elif n = 6 then 8: elif n = 7 then 4: else A283881(n-A283881(n-1)) + A283881(n-A283881(n-2)): fi: end:
%Y A283881 Cf. A005185, A188670, A244477, A269328, A275153, A283880.
%K A283881 nonn
%O A283881 1,1
%A A283881 _Nathan Fox_, Mar 19 2017