|
Search: id:A001768
|
|
|
| A001768 |
|
Sorting numbers: number of comparisons for merge sort of n elements.
(Formerly M2408 N0954)
|
|
+0
4
|
|
| 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; listen)
|
|
|
OFFSET
|
1,3
|
|
|
REFERENCES
|
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.
L. R. Ford, Jr. and S. M. Johnson, A tournament problem, Amer. Math. Monthly, 66 (1959), 387-389.
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.
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).]
|
|
LINKS
|
T. D. Noe, Table of n, a(n) for n=1..1000
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.
Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.
Index entries for sequences related to sorting
|
|
FORMULA
|
Sum ceiling(log_2 (3k/4) ), k=1..n. 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;
|
|
CROSSREFS
|
Sequence in context: A016040 A003070 A036604 this_sequence A089108 A029899 A072166
Adjacent sequences: A001765 A001766 A001767 this_sequence A001769 A001770 A001771
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
Search completed in 0.002 seconds
|
