|
|
A001768
|
|
Sorting numbers: number of comparisons for merge insertion sort of n elements.
(Formerly M2408 N0954)
|
|
7
|
|
|
0, 1, 3, 5, 7, 10, 13, 16, 19, 22, 26, 30, 34, 38, 42, 46, 50, 54, 58, 62, 66, 71, 76, 81, 86, 91, 96, 101, 106, 111, 116, 121, 126, 131, 136, 141, 146, 151, 156, 161, 166, 171, 177, 183, 189, 195, 201, 207, 213, 219, 225, 231, 237, 243, 249, 255
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
REFERENCES
|
D. E. Knuth, Art of Computer Programming, Vol. 3, Sect. 5.3.1.
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.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
Eric Weisstein's World of Mathematics, Sorting
|
|
FORMULA
|
a(n) = Sum_{k=1..n} ceiling(log_2 (3k/4)). See also Problem 5.3.1-14 of Knuth.
a(n) = n(z-1)-[(2^(z+2)-3z)/6] where z = [log_2(3n+3)]. - David W. Wilson, Feb 26 2006
|
|
MAPLE
|
Digits := 60: A001768 := proc(n) local k; add( ceil( log(3*k/4)/log(2) ), k=1..n); end;
# second Maple program:
b:= proc(n) option remember; ceil(log[2](3*n/4)) end:
a:= proc(n) option remember; `if`(n<1, 0, a(n-1)+b(n)) end:
|
|
MATHEMATICA
|
Accumulate[Ceiling[Log[2, (3*Range[60])/4]]] (* Harvey P. Dale, Oct 30 2013 *)
|
|
PROG
|
(Haskell)
a001768 n = n * (z - 1) - (2 ^ (z + 2) - 3 * z) `div` 6
where z = a085423 $ n + 1
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|