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

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

Author

Nathan Fox, Mar 19 2017

Keywords

• nonn

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.

Links

• Nathan Fox, Table of n, a(n) for n = 1..10000
• Index entries for linear recurrences with constant coefficients, signature (1, -1, 1, 1, -1, 1, -1).

Crossrefs

Cf. A005185, A188670, A244477, A264756, A283878.

Programs

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:

Mathematica

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 *)

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.