%I A003071 M2443
%S A003071 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,
%T A003071 101,105,109,115,119,124,129,161,163,166,169,174,177,181,185,194,197,201,
%U A003071 205,211,215,220,225,242,245,249,253,259,263,268,273,283,287,292,297,304
%N A003071 Sorting numbers: maximal number of comparisons for sorting n elements 
               by list merging.
%C A003071 Comment from Jeremy Gardiner, Dec 28 2008: The following sequences all 
               appear to have the same parity: A003071, A029886, A061297, A092524, 
               A093431, A102393, A104258, A122248, A128975.
%D A003071 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%D A003071 J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical 
               Computer Sci., 98 (1992), 163-197.
%D A003071 D. E. Knuth, Art of Computer Programming, Vol. 3, Sections 5.2.4 and 
               5.3.1.
%H A003071 J.-P. Allouche and J. Shallit, <a href="http://www.cs.uwaterloo.ca/~shallit/
               Papers/as0.ps">The ring of k-regular sequences</a>, Theoretical Computer 
               Sci., 98 (1992), 163-197.
%H A003071 <a href="Sindx_So.html#sorting">Index entries for sequences related to 
               sorting</a>
%F A003071 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].
%F A003071 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
%F A003071 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
%Y A003071 Cf. A001855.
%Y A003071 Sequence in context: A167791 A139099 A152259 this_sequence A109324 A047270 
               A084060
%Y A003071 Adjacent sequences: A003068 A003069 A003070 this_sequence A003072 A003073 
               A003074
%K A003071 nonn,easy,nice
%O A003071 1,3
%A A003071 N. J. A. Sloane (njas(AT)research.att.com).
%E A003071 More terms from David W. Wilson (davidwwilson(AT)comcast.net)