A175542 - OEIS

%I #25 Jan 02 2022 17:53:57

%S 1,2,1,4,2,6,1,8,4,10,5,12,6,14,1,16,8,18,9,20,10,22,3,24,12,26,13,28,

%T 14,30,1,32,16,34,17,36,18,38,19,40,20,42,21,44,22,46,23,48,24,50,25,

%U 52,26,54,27,56,28,58,29,60,30,62,1,64,32,66,33,68,34,70,35,72,36,74,37,76

%N Smallest integer t such that 1 + binomial(n,1) + binomial(n,2) + ... + binomial(n,t) is a power of 2.

%C Let C be a binary linear code C(n,k,d) of length n = 2^r - 1 (with r >=2) whose number of information bits k = 2^r - 1 - r and whose minimum distance is d. We have the lower bound 2^(n-k) >= 1 + binomial(n,1) + ... + binomial(n,t) where t = (d-1)/2. Equality holds with perfect codes (Hamming codes with d = 3 or t = 1, the Golay code with d = 7 or t = 3), and in no other nontrivial cases.

%C Property of this sequence:

%C a(n) = 1 for n = 2^m - 1, m = 1,2,... => (Hamming codes C(n, k, 3));

%C a(n) = 3 for n = 23 => 1 + binomial(n,1) + binomial(n,2) + binomial(n,3) = 2^11, and we obtain the Golay code C(23,12,7) consisting of 2^12 = 4096 codewords of length 23 and minimum distance 7.

%C Each integer m >= 2 appears a finite number of times. For example, a(n) = 2 only for n in {2, 5, 90}; a(n) = 3 only for n = 23; a(n) = 4 only for n in {4, 9}; a(n) = 5 only for n = 11 (see MO link). - _Max Alekseyev_, Jan 02 2022

%C a(2n) <= 2n; a(2n+1) <= n. - _Max Alekseyev_, Jan 02 2022

%D R. W. Hamming, Error detecting and correcting codes, Bell Sys. Tech. J., vol. 29, pp. 147-160, 1950.

%D F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North Holland, 1978.

%H Harvey P. Dale, <a href="/A175542/b175542.txt">Table of n, a(n) for n = 1..500</a>

%H M. J. E. Golay, <a href="https://www.lama.univ-savoie.fr/~hyvernat/Enseignement/1617/info528/TP-Golay/golay_paper.pdf ">Notes on digital coding</a>, Proc. IEEE, vol. 37, p. 657, 1949.

%H John D. Cook et al., <a href="https://mathoverflow.net/q/412940">When do binomial coefficients sum to a power of 2?</a>, MathOverflow, 2022.

%H Eric Weisstein, <a href="http://mathworld.wolfram.com/PerfectCode.html">Perfect Code</a>

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Hamming_code">Hamming code</a>.

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Golay_code">Golay code</a>.

%e a(7) = 1 => 1 + binomial(7,1) = 2^3, and we obtain the Hamming code C(7,4), 4 = 7 - 3.

%e a(15) = 1 => 1 + binomial(15,1) = 2^4, and we obtain the Hamming code C(15,11), 11 = 15 - 4.

%e a(23) = 3 => 1 + binomial(23,1) + binomial(23,2) + binomial(23,3) = 2^11, and we obtain the Golay code C(23,12), 12 = 23 - 11.

%p with(numtheory):for n from 1 to 100 do:s:=1:indic:=0:for p from 1 to n do:s:=s+binomial(n,p):for q from 0 to 100 do:x:=2^q:if x=s and indic=0 then indic:=1: printf(`%d, `, q): else fi:od:od:od:

%t pwr2[n_]:=Module[{t=1},While[!IntegerQ[Log[2,Total[Table[Binomial[n,i],{i,t}]]+1]],t++];t]; Array[pwr2,80] (* _Harvey P. Dale_, Mar 06 2012 *)

%K nonn

%O 1,2

%A _Michel Lagneau_, Jun 21 2010