|
%I #14 Mar 08 2024 12:13:02
%S 12,6,4,6,1,6,12,10,4,6,13,6,12,16,4,6,25,6,12,26,4,6,37,6,12,42,4,6,
%T 49,6,12,68,4,6,61,6,12,110,4,6,73,6,12,178,4,6,85,6,12,288,4,6,97,6,
%U 12,466,4,6,109,6,12,754,4,6,121,6,12,1220,4,6,133,6,12,1974,4
%N A linear-recurrent 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(1) = 12, a(2) = 6, a(3) = 4, a(4) = 6, a(5) = 1, a(6) = 6, a(7) = 12, a(8) = 10, a(9) = 4.
%C This sequence is an interleaving of six simpler sequences. Four are constant, one is a linear polynomial, and one is a Fibonacci-like sequence.
%H Nathan Fox, <a href="/A283880/b283880.txt">Table of n, a(n) for n = 1..10000</a>
%H <a href="/index/Rec#order_24">Index entries for linear recurrences with constant coefficients</a>, signature (0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, -2, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 1).
%F a(6n) = 6, a(6n+1) = 12, a(6n+2) = 2*F(n+4), a(6n+3) = 4, a(6n+4) = 6, a(6n+5) = 12n+1.
%F G.f.: (-6*x^23+11*x^22-6*x^21-4*x^20-4*x^19-12*x^18+12*x^16+2*x^13 +12*x^11 -10*x^10 +12*x^9+8*x^8 +8*x^7+24*x^6-6*x^5-x^4-6*x^3-4*x^2 -6*x-12) / ((-1+x^6+x^12) *(-1+x)^2*(1+x)^2*(1+x+x^2)^2*(1-x+x^2)^2).
%F a(n) = 3*a(n-6) - 2*a(n-12) - a(n-18) + a(n-24) for n > 24.
%p A283880:=proc(n) option remember: if n <= 0 then 0: elif n = 1 then 12: elif n = 2 then 6: elif n = 3 then 4: elif n = 4 then 6: elif n = 5 then 1: elif n = 6 then 6: elif n = 7 then 12: elif n = 8 then 10: elif n = 9 then 4: else A283880(n-A283880(n-1)) + A283880(n-A283880(n-2)): fi: end:
%o (Python)
%o from functools import cache
%o @cache
%o def a(n):
%o if n <= 0: return 0
%o if n <= 9: return [12, 6, 4, 6, 1, 6, 12, 10, 4][n-1]
%o return a(n - a(n-1)) + a(n - a(n-2))
%o print([a(n) for n in range(1, 76)]) # _Michael S. Branicky_, Dec 06 2021
%Y Cf. A005185, A188670, A244477, A269328, A275153, A283881.
%K nonn
%O 1,1
%A _Nathan Fox_, Mar 19 2017
|
