|
Search: id:A115777
|
|
|
| A115777 |
|
Levenshtein distance between n considered as a decimal string and n considered as a binary string. |
|
+0
4
|
|
| 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; listen)
|
|
|
OFFSET
|
1,2
|
|
|
COMMENT
|
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
|
Michael Gilleland, Levenshtein Distance [It has been suggested that this algorithm gives incorrect results sometimes. - njas]
|
|
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 this_sequence A072768 A071673 A072660
Adjacent sequences: A115774 A115775 A115776 this_sequence A115778 A115779 A115780
|
|
KEYWORD
|
base,nonn
|
|
AUTHOR
|
Robert G. Wilson v (rgwv(AT)rgwv.com), Jan 26 2006
|
|
|
Search completed in 0.002 seconds
|
