A248327 Levenshtein distance of n and its reversal in decimal representation, cf. A004086.

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 2, 2, 2, 2, 2, 2, 2, 2, 1, 2, 0, 2, 2, 2, 2, 2, 2, 2, 1, 2, 2, 0, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 0, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 0, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 0, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 0, 2, 2, 1, 2, 2, 2, 2, 2

Offset: 0

Author

Reinhard Zumkeller, Oct 05 2014

Keywords

• nonn
• base

Comments

a(n) = number of editing steps (replace, delete and insert) to transform n to A004086(n);

a(A002113(n)) = 0, a(10*A002113(n)) = 1 for n > 0;

a(A248336(n)) = n and a(m) != n for m < A248336(n).

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
• Haskell Wiki, Edit distance
• WikiBooks: Algorithm Implementation, Levenshtein distance
• Wikipedia, Levenshtein distance

Crossrefs

Cf. A004086, A002113, A248336.

Programs

Haskell

a248327 0 = 0
a248327 n = levenshtein (show n) (dropWhile (== '0') $ reverse $ show n)
levenshtein :: (Eq t) => [t] -> [t] -> Int
levenshtein us vs = last $ foldl transform [0..length us] vs where
   transform xs@(x:xs') c = scanl compute (x+1) (zip3 us xs xs') where
      compute z (c', x, y) = minimum [y+1, z+1, x + fromEnum (c' /= c)]