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