cp's OEIS Frontend

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

%I A269328 #27 Mar 03 2024 22:14:49
%S A269328 5,2,0,3,6,5,2,5,5,12,5,2,10,5,18,5,2,15,5,24,5,2,20,5,30,5,2,25,5,36,
%T A269328 5,2,30,5,42,5,2,35,5,48,5,2,40,5,54,5,2,45,5,60,5,2,50,5,66,5,2,55,5,
%U A269328 72,5,2,60,5,78,5,2,65,5,84,5,2,70,5,90
%N A269328 An eventually quasilinear solution to Hofstadter's Q recurrence.
%C A269328 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) = 5, a(2) = 2, a(3) = 0, a(4) = 3, a(5) = 6, a(6) = 5, a(7) = 2.
%C A269328 Starting from n=5, this sequence consists of five interleaved linear sequences with three different slopes.
%C A269328 Square array read by rows: T(j,k), j>=1, 1<=k<=5, in which row j list [5, 2, 5*(j-1), 5, 6*j], except T(1,4) = 3, not 5. - _Omar E. Pol_, Jun 22 2016
%H A269328 Vincenzo Librandi, <a href="/A269328/b269328.txt">Table of n, a(n) for n = 1..10000</a>
%H A269328 Nathan Fox, <a href="https://arxiv.org/abs/1609.06342">Finding Linear-Recurrent Solutions to Hofstadter-Like Recurrences Using Symbolic Computation</a>, arXiv:1609.06342 [math.NT], 2016.
%H A269328 <a href="/index/Rec#order_10">Index entries for linear recurrences with constant coefficients</a>, signature (0, 0, 0, 0, 2, 0, 0, 0, 0, -1).
%F A269328 a(4) = 3; otherwise a(5n) = 6n, a(5n+1) = 5, a(5n+2) = 2, a(5n+3) = 5n, a(5n+4) = 5.
%F A269328 From _Chai Wah Wu_, Jun 22 2016: (Start)
%F A269328 a(n) = 2*a(n-5) - a(n-10) for n > 14.
%F A269328 G.f.: x*(-2*x^13 - x^8 + 5*x^7 - 2*x^6 - 5*x^5 + 6*x^4 + 3*x^3 + 2*x + 5)/(x^10 - 2*x^5 + 1). (End)
%e A269328 From _Omar E. Pol_, Jun 22 2016: (Start)
%e A269328 Written as a square array T(j,k) with five columns the sequence begins:
%e A269328 5, 2,  0, 3,  6;
%e A269328 5, 2,  5, 5, 12;
%e A269328 5, 2, 10, 5, 18;
%e A269328 5, 2, 15, 5, 24;
%e A269328 5, 2, 20, 5, 30;
%e A269328 5, 2, 25, 5, 36;
%e A269328 5, 2, 30, 5, 42;
%e A269328 5, 2, 35, 5, 48;
%e A269328 5, 2, 40, 5, 54;
%e A269328 5, 2, 45, 5, 60;
%e A269328 5, 2, 50, 5, 66;
%e A269328 5, 2, 55, 5, 72;
%e A269328 5, 2, 60, 5, 78;
%e A269328 5, 2, 65, 5, 84;
%e A269328 5, 2, 70, 5, 90;
%e A269328 ...
%e A269328 Note that T(1,4) = 3, not 5. (End)
%t A269328 Join[{5, 2, 0, 3}, LinearRecurrence[{0, 0, 0, 0, 2, 0, 0, 0, 0, -1} , {6, 5, 2, 5, 5, 12, 5, 2, 10, 5}, 80]] (* _Jean-François Alcover_, Dec 16 2018 *)
%t A269328 CoefficientList[Series[(-2 x^13 - x^8 + 5 x^7 - 2 x^6 - 5 x^5 + 6 x^4 + 3 x^3 + 2 x + 5) / (x^10 - 2 x^5 + 1), {x, 0, 100}], x] (* _Vincenzo Librandi_, Dec 16 2018 *)
%o A269328 (Magma) I:=[5,2,0,3,6,5,2,5,5,12,5,2,10,5]; [n le 14 select I[n] else 2*Self(n-5)-Self(n-10): n in [1..100]]; // _Vincenzo Librandi_, Dec 16 2018
%Y A269328 Cf. A005185, A188670, A244477, A264756.
%K A269328 nonn,tabf
%O A269328 1,1
%A A269328 _Nathan Fox_, Feb 23 2016