|
| |
|
|
A003071
|
|
Sorting numbers: maximal number of comparisons for sorting n elements by list merging.
(Formerly M2443)
|
|
20
|
|
|
|
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, 101, 105, 109, 115, 119, 124, 129, 161, 163, 166, 169, 174, 177, 181, 185, 194, 197, 201, 205, 211, 215, 220, 225, 242, 245, 249, 253, 259, 263, 268, 273, 283, 287, 292, 297, 304
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,3
|
|
|
COMMENTS
|
The following sequences all appear to have the same parity: A003071, A029886, A061297, A092524, A093431, A102393, A104258, A122248, A128975. - Jeremy Gardiner, Dec 28 2008
a(A092246(n)) = A230720(n); a(A230709(n)) = A230721(n+1). - Reinhard Zumkeller, Oct 28 2013
|
|
|
REFERENCES
|
D. E. Knuth, Art of Computer Programming, Vol. 3, Sections 5.2.4 and 5.3.1.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
|
Zak Seidov, Table of n, a(n) for n = 1..10000
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.
An Vinh Nguyen Dinh, Nhien Pham Hoang Bao, Terrillon Jean-Christophe, Hiroyuki Iida, Reaper Tournament System, 2018.
An Vinh Nguyen Dinh, Nhien Pham Hoang Bao, Mohd Nor Akmal Khalid, Hiroyuki Iida, Simulating competitiveness and precision in a tournament structure: a reaper tournament system, Int'l J. of Information Technology (2020) Vol. 12, 1-18.
Tanya Khovanova, There are no coincidences, arXiv preprint 1410.2193 [math.CO], 2014.
Index entries for sequences related to sorting
|
|
|
FORMULA
|
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].
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
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
|
|
|
MATHEMATICA
|
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 *)
|
|
|
PROG
|
(Haskell)
a003071 n = 1 - 2 ^ last es +
sum (zipWith (*) (zipWith (+) es [0..]) (map (2 ^) es))
where es = reverse $ a133457_row n
-- Reinhard Zumkeller, Oct 28 2013
|
|
|
CROSSREFS
|
Cf. A001855, A133457.
Sequence in context: A139099 A152259 A219611 * A178442 A319986 A284310
Adjacent sequences: A003068 A003069 A003070 * A003072 A003073 A003074
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
|
AUTHOR
|
N. J. A. Sloane
|
|
|
EXTENSIONS
|
More terms from David W. Wilson
|
|
|
STATUS
|
approved
|
| |
|
|
