|
| |
|
|
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
|
|
|
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
|
|
|
|
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
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
