A360495 -id:A360495 - cp's OEIS frontend

A080804 Least number of connected subgraphs of the binary cube GF(2)^n such that every vertex of GF(2)^n lies in at least one of the subgraphs and no two vertices lie in the same set of subgraphs (such a collection is called an identifying set).

1, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 70, 71, 72, 73, 74, 75, 76, 77, 78

Offset: 1

Pete Rosendahl (perosen(AT)utu.fi), Mar 26 2003

a(n-1) is also the minimum number of matches in a tournament to fairly determine the best two players from n >= 2 contestants. For example, a(8-1) = a(7) = 9 matches are required to determine the best two players from 8 participants. See Steinhaus (1983). - Hugo Pfoertner, Dec 13 2022

Hugo Steinhaus, Mathematical Snapshots, Third American Edition, Oxford University Press, New York, 1983, pp 54-55.

Paolo Xausa, Table of n, a(n) for n = 1..10000
Petri Rosendahl, On the identification problems in products of cycles, Discrete Mathematics, Volume 275, Issue 1, January 2004, pp 277-288.
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions

Second column of A360495.

A080804[n_]:=n+Floor[Log2[n]];Array[A080804,100] (* Paolo Xausa, Sep 26 2023 *)

a(n) = n + floor(log_2(n)).

More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Apr 06 2003

A036604 Sorting numbers: minimal number of comparisons needed to sort n elements.

Original entry on oeis.org

0, 1, 3, 5, 7, 10, 13, 16, 19, 22, 26, 30, 34, 38, 42, 46, 50, 54, 58, 62, 66, 71

Offset: 1

N. J. A. Sloane

The Peczarski paper in Algorithmica has a table giving upper and lower bounds that differ by at most 1. In particular, the values a(20) = 62 and a(21) = 66 are also known. - Bodo Manthey, Mar 01 2007

D. E. Knuth, Art of Computer Programming, Vol. 3, 2nd. edition, Sect. 5.3.1.
E. Reingold, J. Nievergelt and N. Deo, Combinatorial Algorithms, Prentice-Hall, 1977, section 7.4, p. 309.
Tianxing Tao, On optimal arrangement of 12 points, pp. 229-234 in Combinatorics, Computing and Complexity, ed. D. Du and G. Hu, Kluwer, 1989. [Finds a(12).]

Eisa Alanazi, Malek Mouhoub, Sandra Zilles, Interactive Learning of Acyclic Conditional Preference Networks, arXiv:1801.03968 [cs.AI], 2018.
Enrico Iurlano and Günther R. Raidl, SAT-Based Search for Minwise Independent Families, arXiv:2412.11811 [cs.DM], 2024. See p. 5.
Marcin Peczarski, New Results in Minimum-Comparison Sorting, Algorithmica 40(2):133-145, 2004.
Marcin Peczarski, The Ford-Johnson algorithm still unbeaten for less than 47 elements, Information Processing Letters, Volume 101, Issue 3, 14 February 2007, Pages 126-128.
Marcin Peczarski, Towards optimal sorting of 16 elements, arXiv:1108.0866 [cs.DS], 2011.
Marcin Peczarski, Sorting 13 Elements Requires 34 Comparisons, Proc. of the 10th European Symp. on Algorithms (ESA), vol. 2452 of Lecture Notes in Comput. Sci., pp. 785-794. Springer, 2002.
Florian Stober and Armin Weiss, Lower bounds for sorting 16, 17, and 18 elements, 2023 Proc. Symp. Algorithm Engineering and Experiments pp. 201-213, 2023. SIAM; arXiv preprint, arXiv:2206.05597 [cs.DS], 2022.
Index entries for sequences related to sorting

A001768 is an upper bound, A003070 a lower bound.

Cf. A360495.

a(13) was determined by Marcin Peczarski. - Bodo Manthey, Sep 25 2002
a(14)=38 and a(22)=71 were determined by Marcin Peczarski. - Bodo Manthey (manthey(AT)cs.uni-sb.de), Feb 28 2007
a(16)=46, a(17)=50, and a(18)=54 were determined by Stober and Weiss. - Robert McLachlan, May 29 2024
a(19)-a(22) from table in arXiv preprint of Stober and Weiss. - Domotor Palvolgyi, Jun 03 2025

A215476 Minimum number of comparisons needed to find the median of n elements.

Original entry on oeis.org

0, 1, 3, 4, 6, 8, 10, 12, 14, 16, 18, 20, 23

Offset: 1

Jeff Erickson, Aug 12 2012

Dor and Zwick 1999 prove a(n) <= 2.95n + o(n).

Dor and Zwick 2001 prove a(n) >= (2+2^(-80))n - o(n).

D. Dor and U. Zwick, Median selection requires (2+epsilon)n comparisons, SIAM J. Discrete Math 14(3):312-325, 2001.
D. Dor and U. Zwick, Selecting the median, SIAM J. Comput. 28(5):1722-1758, 1999.
D. E. Knuth, The Art of Computer Programming, Vol. 3, 2nd edition, Sect. 5.3.2.
Kenneth Oksanen, Searching for selection algorithms, Elec. Notes Discrete Math. 27:77, 2006.

William Gasarch, Wayne Kelly and William Pugh, Finding the i-th largest of n for small i,n, ACM SIGACT News, Volume 27, Issue 2, June 1996, pp. 88-96.
Kenneth Oksanen, Selecting the i'th largest of n elements. (last modified April 2005)

Cf. A117627, A360495.

a(n) = A360495(n,ceiling(n/2)). - Paolo Xausa, Apr 09 2023

Added three more terms (from Kenneth Oksanen), Jeff Erickson, Aug 13 2012

cp's OEIS Frontend

A374236 Row sums of A360495.

Views

Author

Keywords

Comments

Crossrefs

Formula

A080804 Least number of connected subgraphs of the binary cube GF(2)^n such that every vertex of GF(2)^n lies in at least one of the subgraphs and no two vertices lie in the same set of subgraphs (such a collection is called an identifying set).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A036604 Sorting numbers: minimal number of comparisons needed to sort n elements.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A215476 Minimum number of comparisons needed to find the median of n elements.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions