A061338 Increase in maximal number of comparisons for sorting n elements by list merging.

0, 1, 2, 2, 4, 2, 3, 3, 8, 2, 3, 3, 5, 3, 4, 4, 16, 2, 3, 3, 5, 3, 4, 4, 9, 3, 4, 4, 6, 4, 5, 5, 32, 2, 3, 3, 5, 3, 4, 4, 9, 3, 4, 4, 6, 4, 5, 5, 17, 3, 4, 4, 6, 4, 5, 5, 10, 4, 5, 5, 7, 5, 6, 6, 64, 2, 3, 3, 5, 3, 4, 4, 9, 3, 4, 4, 6, 4, 5, 5, 17, 3, 4, 4, 6, 4, 5, 5, 10, 4, 5, 5, 7, 5, 6, 6, 33, 3, 4, 4

Offset

0,3

Comments

Or, first differences of A003071. - Zak Seidov, Dec 28 2011

Links

Zak Seidov, Table of n, a(n) for n = 0..10000

Index entries for sequences related to sorting

Formula

For n > 0: a(n) = A003071(n) - A003071(n - 1) = A006519(n) + A000120(n) - 1. If n is a power of 2 then a(n) = n, otherwise a(n) = a(A053645(n)) + 1 where A053645(n) = n - 2^floor(log_2(n)) is the amount by which n exceeds a power of 2.

G.f.: x/(1-x)^2 + (1/(1-x))*Sum_{k>=1} (-1 + (1-x)*2^(k-1))*x^2^k/(1-x^2^k). - Ralf Stephan, Apr 17 2003

Mathematica

nn=100; s={1}; m = Ceiling[Log[2, nn]]; Do[s=Join[s, {2^n}, s+1], {n, m}]; Prepend[Take[s, nn], 0] (* Zak Seidov, Dec 28 2011 *)

Prog

(Haskell)
a061338 0 = 0
a061338 n = a006519 n + a000120 n - 1  -- Reinhard Zumkeller, Dec 29 2011

Crossrefs

Cf. A003071.

Sequence in context: A221861 A057939 A163371 * A135714 A103274 A046820

Adjacent sequences: A061335 A061336 A061337 * A061339 A061340 A061341

Keyword

nonn

Author

Henry Bottomley, Apr 27 2001

Status

approved