login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A057591 Maximal size of binary code of length n that corrects 2 deletions. 2
1, 1, 2, 2, 2, 4, 5, 7, 11, 16, 24 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

Comments from Pablo San Segundo, Dec 04 2015 (Start): The search for a maximal clique in the graph 2dc.2048 has now finished. The answer is 24 (which was already known to be a lower bound).

The total time was 16.4 days using a 20-core XEON with 128Gb. 18 cores out of the 20 were in fact used.

The solution was found by a strong heuristic algorithm during pre-processing (about 5s). The actual search time was used “only” to prove optimality. The actual maximum clique algorithm is our most recent variant based on infra-chromatic BBMCX, described here, but as yet unpublished: https://www.researchgate.net/profile/Pablo_San_Segundo

The project was carried out by Pablo San Segundo and Jorge Artieda, Polytechnic University of Madrid (UPM), Center of Automation and Robotics (CAR). Supported by National Grant DPI 2014-53525-C3-1-R (End)

LINKS

Table of n, a(n) for n=1..11.

N. J. A. Sloane, Challenge Problems: Independent Sets in Graphs

N. J. A. Sloane, On single-deletion-correcting codes, in Codes and Designs (Columbus, OH, 2000), 273-291, Ohio State Univ. Math. Res. Inst. Publ., 10, de Gruyter, Berlin, 2002.

N. J. A. Sloane, On single-deletion-correcting codes

CROSSREFS

Cf. A000016, A057608, A057657, A010101.

Sequence in context: A326546 A326685 A274150 * A024405 A230381 A082547

Adjacent sequences:  A057588 A057589 A057590 * A057592 A057593 A057594

KEYWORD

nice,hard,nonn

AUTHOR

N. J. A. Sloane, Oct 05 2000

EXTENSIONS

Guenter Stertenbrink (Sterten(AT)aol.com) found a(9) = 11 and a(10) >= 16, Apr 28 2001

James B. Shearer (jbs(AT)pkmfgvm4.vnet.ibm.com) proved that a(10) = 16, Sep 20 2003

Pablo San Segundo and Jorge Artieda showed that a(11) = 24, Dec 04 2015

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 2 14:47 EDT 2021. Contains 346428 sequences. (Running on oeis4.)