|
| |
|
|
A115777
|
|
Levenshtein distance between n considered as a decimal string and n considered as a binary string.
|
|
3
|
|
|
|
0, 2, 2, 3, 3, 3, 3, 4, 4, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 6, 6, 6, 6, 6, 6, 6, 6, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 5, 5, 6, 6, 7, 7, 7, 7, 7, 7, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 4, 4, 5, 5, 5, 5
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
a(n) = minimal number of editing steps (delete, insert or substitute) to transform n_10 into n_2.
The Levenshtein distance (also called edit distance) between two strings is equal to the minimum number of insertion, deletion, or substitution operations needed to transform one string into the other. It is named after the Russian scientist Vladimir Levenshtein, who developed this metric in 1965. Levenshtein distance is a generalization of Hamming distance.
|
|
|
LINKS
|
Table of n, a(n) for n=1..105.
Michael Gilleland, Levenshtein Distance [It has been suggested that this algorithm gives incorrect results sometimes. - N. J. A. Sloane]
|
|
|
MATHEMATICA
|
levenshtein[s_List, t_List] := Module[{d, n = Length@s, m = Length@t}, Which[s === t, 0, n == 0, m, m == 0, n, s != t, d = Table[0, {m + 1}, {n + 1}]; d[[1, Range[n + 1]]] = Range[0, n]; d[[Range[m + 1], 1]] = Range[0, m]; Do[d[[j + 1, i + 1]] = Min[d[[j, i + 1]] + 1, d[[j + 1, i]] + 1, d[[j, i]] + If[s[[i]] === t[[j]], 0, 1]], {j, m}, {i, n}]; d[[ -1, -1]]]];
f[n_] := levenshtein[ IntegerDigits[n], IntegerDigits[n, 2]]; Array[f, 105]
|
|
|
CROSSREFS
|
Cf. A000027, A007088, first occurrence: A115778.
Sequence in context: A087182 A035453 A097747 * A072768 A071673 A174199
Adjacent sequences: A115774 A115775 A115776 * A115778 A115779 A115780
|
|
|
KEYWORD
|
base,nonn
|
|
|
AUTHOR
|
Robert G. Wilson v, Jan 26 2006
|
|
|
STATUS
|
approved
|
| |
|
|
