A061338 - OEIS

%I #23 Jun 26 2021 20:33:59

%S 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,

%T 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,

%U 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

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

%C Or, first differences of A003071. - _Zak Seidov_, Dec 28 2011

%H Zak Seidov, <a href="/A061338/b061338.txt">Table of n, a(n) for n = 0..10000</a>

%H <a href="/index/So#sorting">Index entries for sequences related to sorting</a>

%F 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.

%F 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

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

%o (Haskell)

%o a061338 0 = 0

%o a061338 n = a006519 n + a000120 n - 1  -- _Reinhard Zumkeller_, Dec 29 2011

%Y Cf. A003071.

%K nonn

%O 0,3

%A _Henry Bottomley_, Apr 27 2001