cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

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).

This page as a plain text file.
%I A080804 #27 Sep 26 2023 03:26:58
%S A080804 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 A080804 30,31,32,33,34,35,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,
%U A080804 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 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).
%C A080804 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 A080804 Hugo Steinhaus, Mathematical Snapshots, Third American Edition, Oxford University Press, New York, 1983, pp 54-55.
%H A080804 Paolo Xausa, <a href="/A080804/b080804.txt">Table of n, a(n) for n = 1..10000</a>
%H A080804 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 A080804 Ralf Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences ...</a>
%H A080804 Ralf Stephan, <a href="/A079944/a079944.ps">Table of generating functions</a>
%F A080804 a(n) = n + floor(log_2(n)).
%t A080804 A080804[n_]:=n+Floor[Log2[n]];Array[A080804,100] (* _Paolo Xausa_, Sep 26 2023 *)
%Y A080804 Second column of A360495.
%K A080804 easy,nonn
%O A080804 1,2
%A A080804 Pete Rosendahl (perosen(AT)utu.fi), Mar 26 2003
%E A080804 More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Apr 06 2003