Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #27 Sep 26 2023 03:26:58
%S 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,
%T 30,31,32,33,34,35,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,
%U 54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,70,71,72,73,74,75,76,77,78
%N 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).
%C 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
%D Hugo Steinhaus, Mathematical Snapshots, Third American Edition, Oxford University Press, New York, 1983, pp 54-55.
%H Paolo Xausa, <a href="/A080804/b080804.txt">Table of n, a(n) for n = 1..10000</a>
%H Petri Rosendahl, <a href="https://doi.org/10.1016/S0012-365X(03)00111-0">On the identification problems in products of cycles</a>, Discrete Mathematics, Volume 275, Issue 1, January 2004, pp 277-288.
%H Ralf Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences ...</a>
%H Ralf Stephan, <a href="/A079944/a079944.ps">Table of generating functions</a>
%F a(n) = n + floor(log_2(n)).
%t A080804[n_]:=n+Floor[Log2[n]];Array[A080804,100] (* _Paolo Xausa_, Sep 26 2023 *)
%Y Second column of A360495.
%K easy,nonn
%O 1,2
%A Pete Rosendahl (perosen(AT)utu.fi), Mar 26 2003
%E More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Apr 06 2003