A081355 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,5

LINKS

Table of n, a(n) for n=0..104.

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

CROSSREFS

Cf. A081356, A002061, A000290, A081230.

Sequence in context: A051486 A218541 A213911 * A223708 A060778 A096492

Adjacent sequences: A081352 A081353 A081354 * A081356 A081357 A081358

KEYWORD

nonn,base

AUTHOR

Reinhard Zumkeller, Mar 18 2003

STATUS

approved