

A275361


An eventually quasilinear solution to Hofstadter's Qrecurrence.


3



0, 4, 40, 9, 8, 8, 7, 1, 5, 13, 24, 1, 8, 8, 8, 1, 5, 13, 8, 7, 8, 8, 23, 1, 5, 13, 8, 15, 8, 16, 31, 1, 5, 13, 24, 23, 8, 24, 39, 1, 5, 13, 40, 31, 8, 32, 47, 1, 5, 13, 56, 39, 8, 40, 55, 1, 5, 13, 72, 47, 8, 48, 63, 1, 5, 13, 88, 55, 8, 56, 71
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

a(n) is the solution to the recurrence relation a(n) = a(na(n1)) + a(na(n2)) [Hofstadter's Q recurrence], with the first 45 terms as initial conditions.
This is a quasilinear sequence with quasiperiod 8. Four of the component sequences are constant, three have slope 1, and one has slope 2.


LINKS

Nathan Fox, Table of n, a(n) for n = 1..1000
Nathan Fox, Finding LinearRecurrent Solutions to HofstadterLike Recurrences Using Symbolic Computation, arXiv:1609.06342 [math.NT], 2016.


FORMULA

a(1) = 0, a(2) = 4, a(14) = 8, a(15) = 8; otherwise:
a(8n) = 1, a(8n+1) = 5, a(8n+2) = 13, a(8n+3) = 16n40, a(8n+4) = 8n9, a(8n+5) = 8, a(8n+6) = 8n8, a(8n+7) = 8n+7.
a(n) = 2*a(n8)  a(n16) for n>31.
G.f.: (7*x^30 8*x^29 14*x^22 +16*x^21 +9*x^17 +5*x^16 +x^15 +6*x^14 24*x^13 +8*x^12 17*x^11 56*x^10 5*x^9 5*x^8 x^7 7*x^6 +8*x^5 8*x^4 +9*x^3 +40*x^2 4*x)/((x1)^2*(x+1)^2*(x^2+1)^2*(x^4+1)^2).


MATHEMATICA

Join[{0, 4, 40, 9, 8, 8, 7, 1, 5, 13, 24, 1, 8, 8, 8}, LinearRecurrence[ {0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 1}, {1, 5, 13, 8, 7, 8, 8, 23, 1, 5, 13, 8, 15, 8, 16, 31}, 100]] (* JeanFrançois Alcover, Dec 12 2018 *)


CROSSREFS

Cf. A005185, A188670, A244477, A264756, A264757, A264758, A268368, A275153, A275362.
Sequence in context: A049475 A264084 A080271 * A274686 A217397 A104292
Adjacent sequences: A275358 A275359 A275360 * A275362 A275363 A275364


KEYWORD

sign


AUTHOR

Nathan Fox, Jul 24 2016


STATUS

approved



