cp's OEIS Frontend

A200310 a(n) = n-1 for n <= 4, otherwise if n is even then a(n) = a(n-5)+2^(n/2), and if n is odd then a(n) = a(n-1)+2^((n-3)/2).

%I A200310 #46 Sep 08 2022 08:46:00
%S A200310 0,1,2,3,5,8,12,18,26,37,53,76,108,154,218,309,437,620,876,1242,1754,
%T A200310 2485,3509,4972,7020,9946,14042,19893,28085,39788,56172,79578,112346,
%U A200310 159157,224693,318316,449388,636634,898778,1273269,1797557,2546540,3595116,5093082,7190234,10186165,14380469
%N A200310 a(n) = n-1 for n <= 4, otherwise if n is even then a(n) = a(n-5)+2^(n/2), and if n is odd then a(n) = a(n-1)+2^((n-3)/2).
%C A200310 This sequence encodes the solution to the problem of finding the number of comparisons needed for optimal merging of 2 elements with n elements. See also A200311, A239100.
%H A200310 R. L. Graham, <a href="http://www.math.ucsd.edu/~ronspubs/71_07_sorting.pdf">On sorting by comparisons</a>, in Proceedings of the ATLAS Symposium, 1971, pp. 263-269
%H A200310 F. K. Hwang, <a href="http://dx.doi.org/10.1137/0209026">Optimal merging of 3 elements with n elements</a>, SIAM J. Comput. 9 (1980), no. 2, 298--320. MR0568816 (82c:68022).
%H A200310 Frank K. Hwang and David N. Deutsch, <a href="http://dx.doi.org/10.1145/321738.321749">A class of merging algorithms</a>, Journal of the ACM (JACM) 20.1 (1973): 148-159. See "O" page 157.
%H A200310 F. K. Hwang and S. Lin, <a href="http://dx.doi.org/10.1007/BF00289521">Optimal merging of 2 elements with n elements</a>, Acta Informatica, 1 (1971), 145-158.
%H A200310 <a href="/index/Rec#order_07">Index entries for linear recurrences with constant coefficients</a>, signature (1,1,-1,1,-1,2,-2).
%F A200310 If n mod 2 = 0 then set k:=n/2 and a(n) = floor(17*2^(k-1)/7) - 1; otherwise set k:=(n+1)/2 and a(n) = floor(12*2^(k-1)/7) - 1.
%F A200310 G.f.:  x^2*(1+x+x^3+x^4+x^5) / ( (x-1)*(2*x^2-1)*(1+x+x^2)*(x^2-x+1) ). - _R. J. Mathar_, Nov 15 2011
%F A200310 From _Wesley Ivan Hurt_, Mar 24 2015: (Start)
%F A200310 a(n) = a(n-1)+a(n-2)-a(n-3)+a(n-4)-a(n-5)+2*a(n-6)-2*a(n-7).
%F A200310 a(n) = floor((29+5(-1)^n)*2^((2n-7-(-1)^n)/4)/7)-1. (End)
%p A200310 A200310 := proc(n)
%p A200310     option remember;
%p A200310     if n =0 then
%p A200310         0 ;
%p A200310     elif n <= 4 then
%p A200310         n-1
%p A200310     else
%p A200310         if n mod 2 = 0 then
%p A200310             procname(n-5)+2^(n/2)
%p A200310         else
%p A200310             procname(n-1)+2^((n-3)/ 2);
%p A200310         fi;
%p A200310     fi;
%p A200310 end proc:
%p A200310 seq(A200310(n),n=1..40) ;
%t A200310 Table[Floor[(29 + 5 (-1)^n)*2^((2n - 7 - (-1)^n)/4)/7] - 1, {n, 50}] (* _Wesley Ivan Hurt_, Mar 24 2015 *)
%t A200310 CoefficientList[Series[x (1 + x + x^3 + x^4 + x^5) / ((x - 1)(2 x^2 - 1) (1 + x + x^2) (x^2 - x + 1)), {x, 0, 50}], x] (* _Vincenzo Librandi_, Mar 25 2015 *)
%o A200310 (Magma) [Floor((29+5*(-1)^n)*2^((2*n-7-(-1)^n)/4)/7)-1 : n in [1..50]]; // _Wesley Ivan Hurt_, Mar 24 2015
%o A200310 (Magma) I:=[0,1,2,3,5,8,12]; [n le 7 select I[n] else Self(n-1)+Self(n-2)-Self(n-3)+Self(n-4)-Self(n-5)+2*Self(n-6)-2*Self(n-7): n in [1..50]]; // _Vincenzo Librandi_, Mar 25 2015
%Y A200310 Cf. A200311, A239100, A260794, A260795.
%K A200310 nonn,easy
%O A200310 1,3
%A A200310 _N. J. A. Sloane_, Nov 15 2011