A081355 Levenshtein distance between n and n^2 in decimal representation.

0, 0, 1, 1, 2, 1, 1, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 2, 2, 3, 2, 3, 1, 2, 2, 2, 3, 2, 2, 3, 4, 4, 3, 3, 3, 4, 4, 3, 3, 4, 3, 4, 3, 3, 4, 4, 3, 2, 3, 4, 4, 4, 3, 3, 4, 4, 4, 2, 3, 4, 3, 4, 3, 3, 4, 3, 3, 3, 3, 4, 3, 3, 3, 2, 4, 3, 4, 3, 3, 3, 3, 4, 3, 3, 4, 4, 3, 3, 3, 4, 4, 4, 2, 2, 3, 3, 3, 2, 2, 3, 3, 3

Offset: 0

Author

Reinhard Zumkeller, Mar 18 2003

Keywords

• nonn
• base

Links

• Michael Gilleland, Levenshtein Distance. [It has been suggested that this algorithm gives incorrect results sometimes. - _N. J. A. Sloane_]

Crossrefs

Cf. A081356, A002061, A000290, A081230.

Programs

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]]; Table[f[n], {n, 0, 104}] (* Robert G. Wilson v, Jan 25 2006 *)