A061338 -id:A061338 - cp's OEIS frontend

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

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

Offset: 1

N. J. A. Sloane

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

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).

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

Cf. A001855, A133457.

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

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 *)

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

More terms from David W. Wilson

A144092 Triangle of Hankel transforms of sequence array of C(n,floor(n/2)).

Original entry on oeis.org

1, 1, 1, 1, 0, 1, 1, -1, 1, 1, 1, 0, 2, 0, 1, 1, 1, 2, -4, 2, 1, 1, 0, 3, 0, 10, 0, 1, 1, -1, 3, 9, 15, -25, 5, 1, 1, 0, 4, 0, 42, 0, 70, 0, 1, 1, 1, 4, -16, 56, 196, 196, -196, 14, 1, 1, 0, 5, 0, 120, 0, 1176

Offset: 0

Paul Barry, Sep 10 2008

The parity matrix A144093 of this array seems to have row sums A061338(n+1).

			Triangle begins
1,
1, 1,
1, 0, 1,
1, -1, 1, 1,
1, 0, 2, 0, 1,
1, 1, 2, -4, 2, 1,
1, 0, 3, 0, 10, 0, 1,
1, -1, 3, 9, 15, -25, 5, 1,
1, 0, 4, 0, 42, 0, 70, 0, 1,
1, 1, 4, -16, 56, 196, 196, -196, 14, 1,
1, 0, 5, 0, 120, 0, 1176, 0, 588, 0, 1

Triangle (-1)^C(k+1,2)*H(n,k) where the k-th column of H(n,k) is the Hankel transform of the k-th column of the array [k<=n]*C(n-k,floor((n-k)/2).

A144093 Parity array of a matrix of Hankel transforms related to C(n,floor(n/2)).

Original entry on oeis.org

1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1

Offset: 0

Paul Barry, Sep 10 2008

Row sums appear to be A061338(n+1).

			Triangle begins
1,
1, 1,
1, 0, 1,
1, 1, 1, 1,
1, 0, 0, 0, 1,
1, 1, 0, 0, 0, 1,
1, 0, 1, 0, 0, 0, 1,
1, 1, 1, 1, 1, 1, 1, 1,
1, 0, 0, 0, 0, 0, 0, 0, 1,
1, 1, 0, 0, 0, 0, 0, 0, 0, 1,
1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1,
1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1,
1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1,
1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1,
1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1

T(n,k)=mod(A144092(n,k),2).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Mathematica

Formula

Extensions

A144092 Triangle of Hankel transforms of sequence array of C(n,floor(n/2)).

Views

Author

Keywords

Comments

Examples

Formula

A144093 Parity array of a matrix of Hankel transforms related to C(n,floor(n/2)).

Views

Author

Keywords

Comments

Examples

Formula