|
|
A003071
|
|
Sorting numbers: maximal number of comparisons for sorting n elements by list merging.
(Formerly M2443)
|
|
20
|
|
|
0, 1, 3, 5, 9, 11, 14, 17, 25, 27, 30, 33, 38, 41, 45, 49, 65, 67, 70, 73, 78, 81, 85, 89, 98, 101, 105, 109, 115, 119, 124, 129, 161, 163, 166, 169, 174, 177, 181, 185, 194, 197, 201, 205, 211, 215, 220, 225, 242, 245, 249, 253, 259, 263, 268, 273, 283, 287, 292, 297, 304
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
|
|
REFERENCES
|
D. E. Knuth, Art of Computer Programming, Vol. 3, Sections 5.2.4 and 5.3.1.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
|
|
FORMULA
|
Let n = 2^e_1 + 2^e_2 + ... + 2^e_t, e_1 > e_2 > ... > e_t >= 0, t >= 1. Then a(n) = 1 - 2^e_t + Sum_{k=1..t} (e_k + k - 1)*2^e_k [Knuth, Problem 14, Section 5.2.4].
G.f.: x/(1-x)^3 + 1/(1-x)^2*Sum(k>=1, (-1+(1-x)*2^(k-1))*x^2^k/(1-x^2^k)). - Ralf Stephan, Apr 17 2003
|
|
MATHEMATICA
|
|
|
PROG
|
(Haskell)
a003071 n = 1 - 2 ^ last es +
sum (zipWith (*) (zipWith (+) es [0..]) (map (2 ^) es))
where es = reverse $ a133457_row n
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|