A001768 - OEIS

%I M2408 N0954 #52 Dec 03 2019 16:22:29

%S 0,1,3,5,7,10,13,16,19,22,26,30,34,38,42,46,50,54,58,62,66,71,76,81,

%T 86,91,96,101,106,111,116,121,126,131,136,141,146,151,156,161,166,171,

%U 177,183,189,195,201,207,213,219,225,231,237,243,249,255

%N Sorting numbers: number of comparisons for merge insertion sort of n elements.

%D D. E. Knuth, Art of Computer Programming, Vol. 3, Sect. 5.3.1.

%D T. A. J. Nicholson, A method for optimizing permutation problems and its industrial applications, pp. 201-217 of D. J. A. Welsh, editor, Combinatorial Mathematics and Its Applications. Academic Press, NY, 1971.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Alois P. Heinz, <a href="/A001768/b001768.txt">Table of n, a(n) for n = 1..10000</a> (first 1000 terms from T. D. Noe)

%H J.-P. Allouche and J. Shallit, <a href="http://www.cs.uwaterloo.ca/~shallit/Papers/as0.ps">The ring of k-regular sequences</a>, Theoretical Computer Sci., 98 (1992), 163-197.

%H J.-P. Allouche and J. Shallit, <a href="http://dx.doi.org/10.1016/0304-3975(92)90001-V">The ring of k-regular sequences</a>, Theoretical Computer Sci., 98 (1992), 163-197.

%H L. R. Ford, Jr. and S. M. Johnson, <a href="http://www.jstor.org/stable/2308750">A tournament problem</a>, Amer. Math. Monthly, 66 (1959), 387-389.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Sorting.html">Sorting</a>

%H <a href="/index/So#sorting">Index entries for sequences related to sorting</a>

%F a(n) = Sum_{k=1..n} ceiling(log_2 (3k/4)). See also Problem 5.3.1-14 of Knuth.

%F a(n) = n(z-1)-[(2^(z+2)-3z)/6] where z = [log_2(3n+3)]. - _David W. Wilson_, Feb 26 2006

%p Digits := 60: A001768 := proc(n) local k; add( ceil( log(3*k/4)/log(2) ), k=1..n); end;

%p # second Maple program:

%p b:= proc(n) option remember; ceil(log[2](3*n/4)) end:

%p a:= proc(n) option remember; `if`(n<1, 0, a(n-1)+b(n)) end:

%p seq(a(n), n=1..61);  # _Alois P. Heinz_, Dec 03 2019

%t Accumulate[Ceiling[Log[2,(3*Range[60])/4]]] (* _Harvey P. Dale_, Oct 30 2013 *)

%o (PARI) a(n)=ceil(log(3/4*n)/log(2)) \\ _Charles R Greathouse IV_, Nov 04 2011

%o (Haskell)

%o a001768 n = n * (z - 1) - (2 ^ (z + 2) - 3 * z) `div` 6

%o    where z = a085423 $ n + 1

%o -- _Reinhard Zumkeller_, Mar 16 2013  after _David W. Wilson_'s formula.

%Y Cf. A085423, A000523.

%K nonn,easy,nice

%O 1,3

%A _N. J. A. Sloane_

%E Name clarified by _Li-yao Xia_, Nov 18 2015