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,2

Comments

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

References

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

Links

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

Formula

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

Mathematica

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

Crossrefs

Second column of A360495.

Sequence in context: A039093 A085925 A107907 * A164386 A111909 A184010

Adjacent sequences: A080801 A080802 A080803 * A080805 A080806 A080807

Keyword

easy,nonn

Author

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

Extensions

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

Status

approved