Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the 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