A230380 The size of an optimal binary code of length n and edit distance 4.

1, 2, 2, 4, 5, 9, 13, 21

Offset: 3

Author

Sheridan Houghten, Oct 17 2013

Keywords

• nonn
• more

Comments

The edit distance between two words u and v is defined as the minimum number of deletions, insertions, or substitutions required to change u to v.

a(11) >= 32, a(12) >= 54. These lower bounds improve those for a(n) = E_2(n,4) given by the Houghten link (as of March 2024). Examples of codes attaining these bounds are (representing the binary strings as decimal numbers) {0, 63, 85, 150, 243, 252, 263, 281, 356, 417, 479, 538, 610, 680, 887, 915, 924, 1052, 1127, 1136, 1405, 1429, 1446, 1539, 1631, 1644, 1701, 1808, 1935, 1988, 2033, 2046} and {0, 51, 86, 207, 249, 269, 353, 378, 404, 612, 664, 831, 851, 897, 989, 1091, 1128, 1271, 1365, 1502, 1551, 1554, 1628, 1910, 1943, 1956, 2019, 2040, 2076, 2117, 2160, 2321, 2399, 2502, 2583, 2650, 2690, 2937, 3050, 3161, 3198, 3204, 3431, 3483, 3489, 3564, 3585, 3691, 3741, 3752, 3870, 3888, 4032, 4095}, respectively. These codes were found by a simulated annealing search, with the objective function given by the cardinality of a set of binary strings minus a penalty factor times the number of pairs in the set at distance less than 4. - Pontus von Brömssen, Mar 20 2024

Links

• Sheridan Houghten, A Table of Bounds on Optimal Fixed-Length Binary Edit-Metric Codes

Crossrefs

Cf. A005864, A179183, A230381.