login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A003071 Sorting numbers: maximal number of comparisons for sorting n elements by list merging.
(Formerly M2443)
20

%I M2443

%S 0,1,3,5,9,11,14,17,25,27,30,33,38,41,45,49,65,67,70,73,78,81,85,89,

%T 98,101,105,109,115,119,124,129,161,163,166,169,174,177,181,185,194,

%U 197,201,205,211,215,220,225,242,245,249,253,259,263,268,273,283,287,292,297,304

%N Sorting numbers: maximal number of comparisons for sorting n elements by list merging.

%C The following sequences all appear to have the same parity: A003071, A029886, A061297, A092524, A093431, A102393, A104258, A122248, A128975. - _Jeremy Gardiner_, Dec 28 2008

%C a(A092246(n)) = A230720(n); a(A230709(n)) = A230721(n+1). - _Reinhard Zumkeller_, Oct 28 2013

%D J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.

%D D. E. Knuth, Art of Computer Programming, Vol. 3, Sections 5.2.4 and 5.3.1.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Moshe Levin, <a href="/A003071/b003071.txt">Table of n, a(n) for n = 1..10000</a>

%H 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 Tanya Khovanova, <a href="http://arxiv.org/abs/1410.2193">There are no coincidences</a>, arXiv preprint 1410.2193, 2014

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

%F 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_{k=1..t} (e_k + k - 1)*2^e_k [Knuth, Problem 14, Section 5.2.4].

%F 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_, Apr 27 2001

%F 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_, Apr 17 2003

%t a[1] = 0; a[n_] := a[n] = a[n-1] + 2^IntegerExponent[n-1, 2] + DigitCount[n-1, 2, 1] - 1; Table[a[n], {n, 1, 61}] (* _Jean-Fran├žois Alcover_, Feb 10 2012, after _Henry Bottomley_ *)

%o (Haskell)

%o a003071 n = 1 - 2 ^ last es +

%o sum (zipWith (*) (zipWith (+) es [0..]) (map (2 ^) es))

%o where es = reverse $ a133457_row n

%o -- _Reinhard Zumkeller_, Oct 28 2013

%Y Cf. A001855.

%Y Cf. A133457.

%K nonn,easy,nice

%O 1,3

%A _N. J. A. Sloane_

%E More terms from _David W. Wilson_

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 22 14:49 EDT 2018. Contains 316488 sequences. (Running on oeis4.)