|
Search: id:A003071
|
|
|
| A003071 |
|
Maximal number of comparisons for sorting n elements by list merging.
(Formerly M2443)
|
|
+0
5
|
|
| 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; listen)
|
|
|
OFFSET
|
1,3
|
|
|
REFERENCES
|
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.
D. E. Knuth, Art of Computer Programming, Vol. 3, Sections 5.2.4 and 5.3.1.
|
|
LINKS
|
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.
Index entries for sequences related to sorting
|
|
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_{1<=k<=t} (e_k+k-1)*2^e_k [Knuth, Problem 14, Section 5.2.4].
a(n) = a(n-1) + A061338(n) = a(n-1) + A006519(n) + A000120(n)-1 = n + A000337(A000523(n)) + a(n-2^A000523(n)). a(2^k) = k*2^k + 1 = A002064(k). - Henry Bottomley (se16(AT)btinternet.com), Apr 27 2001
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 (ralf(AT)ark.in-berlin.de), Apr 17 2003
|
|
CROSSREFS
|
Cf. A001855.
Adjacent sequences: A003068 A003069 A003070 this_sequence A003072 A003073 A003074
Sequence in context: A047623 A007950 A034936 this_sequence A109324 A047270 A084060
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
njas
|
|
EXTENSIONS
|
More terms from David W. Wilson (davidwwilson(AT)comcast.net)
|
|
|
Search completed in 0.002 seconds
|
