login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A175542 Smallest integer t such that 1 + binomial(n,1) + binomial(n,2) + ... + binomial(n,t) is a power of 2. 1
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 (list; graph; refs; listen; history; text; internal format)
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: A306408 A232626 A322250 * A076686 A114810 A300718

Adjacent sequences:  A175539 A175540 A175541 * A175543 A175544 A175545

KEYWORD

nonn

AUTHOR

Michel Lagneau, Jun 21 2010

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 26 20:04 EDT 2022. Contains 354885 sequences. (Running on oeis4.)