cp's OEIS Frontend

A005864 The coding-theoretic function A(n,4).

%I A005864 M1111 #92 May 08 2025 00:23:55
%S A005864 1,1,1,2,2,4,8,16,20,40,72,144,256,512,1024,2048
%N A005864 The coding-theoretic function A(n,4).
%C A005864 Since A(n,3) = A(n+1,4), A(n,3) gives essentially the same sequence.
%C A005864 The next term a(17) is in the range 2816-3276.
%C A005864 Let T_n be the set of SDS-maps of sequential dynamical systems defined over the complete graph K_n in which all vertices have the same vertex function (defined using a set of two possible vertex states). Then a(n) is the maximum number of period-2 orbits that a function in T_n can have. - _Colin Defant_, Sep 15 2015
%C A005864 Since the n-halved cube graph is isomorphic to (or, if you prefer, defined as) the graph with binary sequences of length n-1 as nodes and edges between pairs of sequences that differ in at most two positions, the independence number of the n-halved cube graph is A(n-1,3) = a(n). - _Pontus von Brömssen_, Dec 12 2018
%C A005864 a(2^k) = A(2^k-1, 3) = 2^(2^k-k-1) because the hypercube Q(2^k-1) can be perfectly packed with radius-1 spheres, corresponding to a Hamming(2^k-1, 2^k-k-1) code. - _Yifan Xie_, May 06 2025
%D A005864 J. H. Conway and N. J. A. Sloane, "Sphere Packings, Lattices and Groups", Springer-Verlag, p. 248.
%D A005864 F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, Elsevier-North Holland, 1978, p. 674.
%D A005864 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A005864 A. E. Brouwer, <a href="http://www.win.tue.nl/~aeb/codes/binary-1.html">Tables of general binary codes</a>
%H A005864 A. E. Brouwer, J. B. Shearer, N. J. A. Sloane and W. D. Smith, <a href="http://dx.doi.org/10.1109/18.59932">New table of constant weight codes</a>, IEEE Trans. Info. Theory 36 (1990), 1334-1380.
%H A005864 Colin Defant, <a href="http://arxiv.org/abs/1509.03907">Binary Codes and Period-2 Orbits of Sequential Dynamical Systems</a>, arXiv:1509.03907 [math.CO], 2015.
%H A005864 Moshe Milshtein, <a href="http://dx.doi.org/10.1016/j.ipl.2015.07.001">A new binary code of length 16 and minimum distance 3</a>, Information Processing Letters 115.12 (2015): 975-976.
%H A005864 Patric R. J. Östergård (patric.ostergard(AT)hut.fi), T. Baicheva and E. Kolev, <a href="http://saturn.hut.fi/~pat/">Optimal binary one-error-correcting codes of length 10 have 72 codewords</a>, IEEE Trans. Inform. Theory, 45 (1999), 1229-1231.
%H A005864 A. M. Romanov, <a href="https://www.mathnet.ru/eng/ppi1192">New binary codes with minimal distance 3</a>, Problemy Peredachi Informatsii, 19 (1983) 101-102.
%H A005864 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Error-CorrectingCode.html">Error-Correcting Code</a>
%H A005864 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/HalvedCubeGraph.html">Halved Cube Graph</a>
%H A005864 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/IndependenceNumber.html">Independence Number</a>
%H A005864 Wikipedia, <a href="https://en.wikipedia.org/wiki/Halved_cube_graph">Halved cube graph</a>
%H A005864 <a href="/index/Aa#And">Index entries for sequences related to A(n,d)</a>
%Y A005864 Cf. A005865: A(n,6) ~ A(n,5), A005866: A(n,8) ~ A(n,7).
%Y A005864 Cf. A001839: A(n,4,3), A001843: A(n,4,4), A169763: A(n,4,5).
%K A005864 nonn,hard,nice,more
%O A005864 1,4
%A A005864 _N. J. A. Sloane_