|
%I M2443 #57 Feb 05 2020 23:51:23
%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 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 Zak Seidov, <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 J.-P. Allouche and J. Shallit, <a href="http://dx.doi.org/10.1016/0304-3975(92)90001-V">The ring of k-regular sequences</a>, Theoretical Computer Sci., 98 (1992), 163-197.
%H An Vinh Nguyen Dinh, Nhien Pham Hoang Bao, Terrillon Jean-Christophe, Hiroyuki Iida, <a href="https://www.researchgate.net/profile/Hiroyuki_Iida3/publication/327274115_Reaper_Tournament_System/links/5b85df07299bf1d5a72ea3db/Reaper-Tournament-System.pdf">Reaper Tournament System</a>, 2018.
%H An Vinh Nguyen Dinh, Nhien Pham Hoang Bao, Mohd Nor Akmal Khalid, Hiroyuki Iida, <a href="https://doi.org/10.1007/s41870-019-00397-5">Simulating competitiveness and precision in a tournament structure: a reaper tournament system</a>, Int'l J. of Information Technology (2020) Vol. 12, 1-18.
%H Tanya Khovanova, <a href="http://arxiv.org/abs/1410.2193">There are no coincidences</a>, arXiv preprint 1410.2193 [math.CO], 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, A133457.
%K nonn,easy,nice
%O 1,3
%A _N. J. A. Sloane_
%E More terms from _David W. Wilson_
|
