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

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, 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, 12, 466, 4, 6, 109, 6, 12, 754, 4, 6, 121, 6, 12, 1220, 4, 6, 133, 6, 12, 1974, 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) = 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.

This sequence is an interleaving of six simpler sequences. Four are constant, one is a linear polynomial, and one is a Fibonacci-like sequence.

Links

Nathan Fox, Table of n, a(n) for n = 1..10000

Index entries for linear recurrences with constant coefficients, 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).

Formula

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.

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

a(n) = 3*a(n-6) - 2*a(n-12) - a(n-18) + a(n-24) for n > 24.

Maple

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:

Prog

(Python)
from functools import cache
@cache
def a(n):
    if n <= 0: return 0
    if n <= 9: return [12, 6, 4, 6, 1, 6, 12, 10, 4][n-1]
    return a(n - a(n-1)) + a(n - a(n-2))
print([a(n) for n in range(1, 76)]) # Michael S. Branicky, Dec 06 2021

Crossrefs

Cf. A005185, A188670, A244477, A269328, A275153, A283881.

Sequence in context: A033332 A051725 A070292 * A084067 A240537 A227354

Adjacent sequences: A283877 A283878 A283879 * A283881 A283882 A283883

Keyword

nonn

Author

Nathan Fox, Mar 19 2017

Status

approved