

A283881


A linearrecurrent solution to Hofstadter's Q recurrence.


2



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, 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, 7, 56, 72, 7, 7, 2048, 4, 7, 63, 80, 7, 7, 4096, 4, 7, 70, 88, 7, 7
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


COMMENTS

a(n) is the solution to the recurrence relation a(n) = a(na(n1)) + a(na(n2)) [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.
This sequence is an interleaving of seven simpler sequences. Four are constant, two are linear polynomials, and one is a geometric sequence.


LINKS

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


FORMULA

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).
G.f.: (8*x^208*x^1914*x^1814*x^17+14*x^1514*x^14+12*x^13 +16*x^12 +21*x^11 +21*x^10+16*x^97*x^8+21*x^74*x^68*x^57*x^47*x^3 8*x^27) / ((1+2*x^7)*(1+x)^2*(1+x+x^2+x^3+x^4+x^5+x^6)^2).
a(n) = 4*a(n7)  5*a(n14) + 2*a(n21) for n > 21.


MAPLE

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(nA283881(n1)) + A283881(nA283881(n2)): fi: end:


CROSSREFS

Cf. A005185, A188670, A244477, A269328, A275153, A283880.
Sequence in context: A198939 A290372 A190410 * A178308 A320377 A213186
Adjacent sequences: A283878 A283879 A283880 * A283882 A283883 A283884


KEYWORD

nonn


AUTHOR

Nathan Fox, Mar 19 2017


STATUS

approved



