A230380 - OEIS

%I #22 Mar 22 2024 09:17:02

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

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

%C 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.

%C 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

%H Sheridan Houghten, <a href="http://www.cosc.brocku.ca/~houghten/binaryedit.html">A Table of Bounds on Optimal Fixed-Length Binary Edit-Metric Codes</a>

%Y Cf. A005864, A179183, A230381.

%K nonn,more

%O 3,2

%A _Sheridan Houghten_, Oct 17 2013