cp's OEIS Frontend

A000983 Size of minimal binary covering code of length n and covering radius 1.

%I A000983 M0329 N0124 #83 Feb 16 2025 08:32:22
%S A000983 1,2,2,4,7,12,16,32,62
%N A000983 Size of minimal binary covering code of length n and covering radius 1.
%C A000983 For k > 0, a(2^k-1) = 2^(2^k-k-1). In this case the minimal covering code is also a Hamming code.
%C A000983 In the game described in the Wikipedia link, with n players, the optimal strategy wins with probability 1-a(n)/2^n. In the optimal strategy, the players first agree on a minimal covering code of length n. After the hats are placed, each player knows two words of length n such that one of them is the hat colors of the n players. If one of these two words is a member of the covering code and the other word is not, that player guesses the word that is not. Otherwise, that player does not guess. This strategy guarantees that the team wins for all words that are not members of the covering code.
%C A000983 Because each codeword covers n+1 of the 2^n words, A053637(n+1) is a lower bound. - _Rob Pratt_, Jan 05 2015
%C A000983 a(n) is also the domination number of the n-hypercube graph Q_n. - _Eric W. Weisstein_, Feb 20 2016
%C A000983 The next term a(10) is in the range 107-120. - _Andrey Zabolotskiy_, Sep 01 2016
%D A000983 G. D. Cohen et al., Covering Codes, North-Holland, 1997, p. 166.
%D A000983 I. S. Honkala and Patric R. J. Östergård, Code design, Chapter 13 of Local Search in Combinatorial Optimization, E. Aarts and J. K. Lenstra (editors), Wiley, New York 1997, pp. 441-456.
%D A000983 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A000983 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A000983 Jernej Azarija, M. A. Henning, S. Klavzar, <a href="https://arxiv.org/abs/1606.08143">(Total) Domination in Prisms</a>, arXiv preprint arXiv:1606.08143 [math.CO], 2016. See Table 1.
%H A000983 R. Bertolo, Patric R. J. Östergård and W. D. Weakley, <a href="http://dx.doi.org/10.1002/jcd.20008">An updated table of binary/ternary mixed covering codes</a>, J. Combin. Designs, 12 (2004), 157-176, DOI:10.1002/jcd.20008. [a(10)>=107]
%H A000983 H. Hamalainen et al., <a href="http://www.jstor.org/stable/2974552">Football pools - a game for mathematicians</a>, Amer. Math. Monthly, 102 (1995), 579-588.
%H A000983 J. G. Kalbfleisch and R. G. Stanton, <a href="https://doi.org/10.1112/jlms/s1-44.1.60">A combinatorial problem in matching</a>, J. London Math. Soc., 44 (1969), 60-64.
%H A000983 Dmitry Kamenetsky, <a href="/A000983/a000983.txt">Best known solutions for n <= 11.</a>
%H A000983 A. Lobstein, G. Cohen and N. J. A. Sloane, <a href="http://gallica.bnf.fr/ark:/12148/bpt6k5494233r/f15.image">Recouvrements d'Espaces de Hamming Binaires</a>, C. R. Acad. Sci. Paris, Series I, 301 (1985), 135-138.
%H A000983 Patric R. J. Östergård and Markku K. Kaikkonen, <a href="http://dx.doi.org/10.1016/S0012-365X(97)81825-0">New upper bounds for binary covering codes</a>, Discrete Mathematics 178 (1998), 165-179.
%H A000983 Patric R. J. Östergård and U. Blass, <a href="http://dx.doi.org/10.1109/18.945268">On the size of optimal binary codes of length 9 and covering radius 1</a>, IEEE Trans. Inform. Theory, 47 (2001), 2556-2557. [Determines a(9)].
%H A000983 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/DominationNumber.html">Domination Number</a>
%H A000983 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/HypercubeGraph.html">Hypercube Graph</a>
%H A000983 Wikipedia, <a href="https://en.wikipedia.org/wiki/Hat_puzzle#Ebert.27s_version_and_Hamming_codes">Hat puzzle (Ebert's version and Hamming codes)</a>
%H A000983 <a href="/index/Coa#covcod">Index entries for sequences related to covering codes</a>
%Y A000983 A column of A060438. Cf. A029866.
%K A000983 nonn,hard,more,nice
%O A000983 1,2
%A A000983 _N. J. A. Sloane_