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

Author

Henry Bottomley, Apr 27 2001

Keywords

• nonn

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

Crossrefs

Cf. A003071.

Programs

Haskell

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

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 *)

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