login
A283879
An eventually quasilinear solution to Hofstadter's Q recurrence.
3
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, 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, 55, 1, 4, 60, 59, 1, 4, 64, 63, 1, 4, 68, 67, 1, 4, 72, 71, 1, 4
OFFSET
1,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(1) = 4, a(2) = 1, a(3) = 0, a(4) = 3, a(5) = 3, a(6) = 1, a(7) = 4, a(8) = 8.
FORMULA
a(1) = 4, a(4) = 3; otherwise a(4n) = 4n, a(4n+1) = 4n-1, a(4n+2) = 1, a(4n+3) = 4.
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).
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.
MAPLE
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:
CROSSREFS
KEYWORD
nonn
AUTHOR
Nathan Fox, Mar 19 2017
STATUS
approved