A106432 Levenshtein distance between successive powers of 2 in decimal representation.

1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 5, 5, 5, 6, 6, 5, 6, 6, 6, 6, 8, 8, 8, 9, 9, 8, 8, 8, 9, 8, 10, 10, 8, 10, 10, 11, 11, 11, 11, 10, 11, 13, 14, 13, 13, 14, 12, 11, 14, 10, 12, 14, 12, 16, 17, 16, 17, 17, 16, 15, 18, 17, 17, 18, 18, 17, 18, 20, 17, 16, 21, 19, 19, 20, 22, 20, 22, 21

Offset: 0

Author

Reinhard Zumkeller, Jan 22 2006

Keywords

• nonn
• base

Comments

a(n) = minimal number of editing steps (delete, insert or substitute) to transform 2^n into 2^(n+1) in decimal representation;

a(n) <= A034887(n).

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 0..1000
• Michael Gilleland, Levenshtein Distance [It has been suggested that this algorithm gives incorrect results sometimes. - _N. J. A. Sloane_]
• Haskell Wiki, Edit distance
• WikiBooks: Algorithm Implementation, Levenshtein Distance
• Wikipedia, Edit Distance
• Wikipedia, Levenshtein Distance

Crossrefs

Cf. A000079.

Programs

Haskell

-- import Data.Function (on)
a106432 n = a106432_list !! n
a106432_list = zipWith (levenshtein `on` show)
                       a000079_list $ tail a000079_list where
   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)]
-- Reinhard Zumkeller, Nov 10 2013

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]] ]]; Table[ levenshtein[IntegerDigits[2^n], IntegerDigits[2^(n + 1)]], {n, 0, 80}] (* Robert G. Wilson v *)

Extensions

More terms from Robert G. Wilson v, Jan 25 2006