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