%I A001768 M2408 N0954
%S A001768 0,1,3,5,7,10,13,16,19,22,26,30,34,38,42,46,50,54,58,62,66,71,76,
%T A001768 81,86,91,96,101,106,111,116,121,126,131,136,141,146,151,156,161,
%U A001768 166,171,177,183,189,195,201,207,213,219,225,231,237,243,249,255
%N A001768 Sorting numbers: number of comparisons for merge sort of n elements.
%D A001768 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%D A001768 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 
               (includes this sequence).
%D A001768 J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical 
               Computer Sci., 98 (1992), 163-197.
%D A001768 L. R. Ford, Jr. and S. M. Johnson, A tournament problem, Amer. Math. 
               Monthly, 66 (1959), 387-389.
%D A001768 D. E. Knuth, Art of Computer Programming, Vol. 3, Sect. 5.3.1.
%D A001768 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 A001768 Tianxing Tao, On optimal arrangement of 12 points, pp. 229-234 in Combinatorics, 
               Computing and Complexity, ed. D. Du and G. Hu, Kluwer, 1989. [Finds 
               a(12).]
%H A001768 T. D. Noe, <a href="b001768.txt">Table of n, a(n) for n=1..1000</a>
%H A001768 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 A001768 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
               Sorting.html">Link to a section of The World of Mathematics.</a>
%H A001768 <a href="Sindx_So.html#sorting">Index entries for sequences related to 
               sorting</a>
%F A001768 Sum ceiling(log_2 (3k/4) ), k=1..n. See also Problem 5.3.1-14 of Knuth.
%F A001768 a(n) = n(z-1)-[(2^(z+2)-3z)/6] where z = [log_2(3n+3)]. - David W. Wilson, 
               Feb 26 2006
%p A001768 Digits := 60: A001768 := proc(n) local k; add( ceil( log(3*k/4)/log(2) 
               ), k=1..n); end;
%Y A001768 Sequence in context: A016040 A003070 A036604 this_sequence A089108 A029899 
               A072166
%Y A001768 Adjacent sequences: A001765 A001766 A001767 this_sequence A001769 A001770 
               A001771
%K A001768 nonn,easy,nice
%O A001768 1,3
%A A001768 N. J. A. Sloane (njas(AT)research.att.com).