login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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). 5
0, 1, 2, 3, 5, 8, 12, 18, 26, 37, 53, 76, 108, 154, 218, 309, 437, 620, 876, 1242, 1754, 2485, 3509, 4972, 7020, 9946, 14042, 19893, 28085, 39788, 56172, 79578, 112346, 159157, 224693, 318316, 449388, 636634, 898778, 1273269, 1797557, 2546540, 3595116, 5093082, 7190234, 10186165, 14380469 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

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.

LINKS

Table of n, a(n) for n=1..47.

R. L. Graham, On sorting by comparisons, in Proceedings of the ATLAS Symposium, 1971, pp. 263-269

F. K. Hwang, Optimal merging of 3 elements with n elements, SIAM J. Comput. 9 (1980), no. 2, 298--320. MR0568816 (82c:68022).

Frank K. Hwang and David N. Deutsch, A class of merging algorithms, Journal of the ACM (JACM) 20.1 (1973): 148-159. See "O" page 157.

F. K. Hwang and S. Lin, Optimal merging of 2 elements with n elements, Acta Informatica, 1 (1971), 145-158.

Index entries for linear recurrences with constant coefficients, signature (1,1,-1,1,-1,2,-2).

FORMULA

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.

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

From Wesley Ivan Hurt, Mar 24 2015: (Start)

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

a(n) = floor((29+5(-1)^n)*2^((2n-7-(-1)^n)/4)/7)-1. (End)

MAPLE

A200310 := proc(n)

    option remember;

    if n =0 then

        0 ;

    elif n <= 4 then

        n-1

    else

        if n mod 2 = 0 then

            procname(n-5)+2^(n/2)

        else

            procname(n-1)+2^((n-3)/ 2);

        fi;

    fi;

end proc:

seq(A200310(n), n=1..40) ;

MATHEMATICA

Table[Floor[(29 + 5 (-1)^n)*2^((2n - 7 - (-1)^n)/4)/7] - 1, {n, 50}] (* Wesley Ivan Hurt, Mar 24 2015 *)

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

PROG

(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

(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

CROSSREFS

Cf. A200311, A239100, A260794, A260795.

Sequence in context: A084376 A098693 A122928 * A001524 A280278 A136275

Adjacent sequences:  A200307 A200308 A200309 * A200311 A200312 A200313

KEYWORD

nonn,easy

AUTHOR

N. J. A. Sloane, Nov 15 2011

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 24 21:33 EST 2018. Contains 299628 sequences. (Running on oeis4.)