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

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, 14, 30, 1, 32, 16, 34, 17, 36, 18, 38, 19, 40, 20, 42, 21, 44, 22, 46, 23, 48, 24, 50, 25, 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

Offset

1,2

Comments

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.

Property of this sequence:

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

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.

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

a(2n) <= 2n; a(2n+1) <= n. - Max Alekseyev, Jan 02 2022

References

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

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

Links

Harvey P. Dale, Table of n, a(n) for n = 1..500

M. J. E. Golay, Notes on digital coding, Proc. IEEE, vol. 37, p. 657, 1949.

John D. Cook et al., When do binomial coefficients sum to a power of 2?, MathOverflow, 2022.

Eric Weisstein, Perfect Code

Wikipedia, Hamming code.

Wikipedia, Golay code.

Example

a(7) = 1 => 1 + binomial(7,1) = 2^3, and we obtain the Hamming code C(7,4), 4 = 7 - 3.
a(15) = 1 => 1 + binomial(15,1) = 2^4, and we obtain the Hamming code C(15,11), 11 = 15 - 4.
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.

Maple

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:

Mathematica

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

Crossrefs

Sequence in context: A232626 A375124 A322250 * A076686 A114810 A300718

Adjacent sequences: A175539 A175540 A175541 * A175543 A175544 A175545

Keyword

nonn

Author

Michel Lagneau, Jun 21 2010

Status

approved