|
%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
|
