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

Author

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

Keywords

• easy
• nonn

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

Crossrefs

Second column of A360495.

Programs

Mathematica

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

Formula

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

Extensions

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