A115777 - OEIS

A115777

Levenshtein distance between n considered as a decimal string and n considered as a binary string.

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.

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: A366664 A097747 A285717 * A340033 A316847 A072768

Adjacent sequences: A115774 A115775 A115776 * A115778 A115779 A115780

KEYWORD

base,nonn

AUTHOR

Robert G. Wilson v, Jan 26 2006

STATUS

approved