cp's OEIS Frontend

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

%I A106432 #13 Nov 10 2013 06:28:35
%S A106432 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,
%T A106432 10,8,10,10,11,11,11,11,10,11,13,14,13,13,14,12,11,14,10,12,14,12,16,
%U A106432 17,16,17,17,16,15,18,17,17,18,18,17,18,20,17,16,21,19,19,20,22,20,22,21
%N A106432 Levenshtein distance between successive powers of 2 in decimal representation.
%C A106432 a(n) = minimal number of editing steps (delete, insert or substitute) to transform 2^n into 2^(n+1) in decimal representation;
%C A106432 a(n) <= A034887(n).
%H A106432 Reinhard Zumkeller, <a href="/A106432/b106432.txt">Table of n, a(n) for n = 0..1000</a>
%H A106432 Michael Gilleland, <a href="http://www.merriampark.com/ld.htm">Levenshtein Distance</a> [It has been suggested that this algorithm gives incorrect results sometimes. - _N. J. A. Sloane_]
%H A106432 Haskell Wiki, <a href="http://www.haskell.org/haskellwiki/Edit_distance">Edit distance</a>
%H A106432 WikiBooks: Algorithm Implementation, <a href="http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance">Levenshtein Distance</a>
%H A106432 Wikipedia, <a href="http://en.wikipedia.org/wiki/Edit_distance">Edit Distance</a>
%H A106432 Wikipedia, <a href="http://en.wikipedia.org/wiki/Levenshtein_distance">Levenshtein Distance</a>
%t A106432 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_ *)
%o A106432 (Haskell)
%o A106432 -- import Data.Function (on)
%o A106432 a106432 n = a106432_list !! n
%o A106432 a106432_list = zipWith (levenshtein `on` show)
%o A106432                        a000079_list $ tail a000079_list where
%o A106432    levenshtein us vs = last $ foldl transform [0..length us] vs where
%o A106432       transform xs@(x:xs') c = scanl compute (x+1) (zip3 us xs xs') where
%o A106432          compute z (c', x, y) = minimum [y+1, z+1, x + fromEnum (c' /= c)]
%o A106432 -- _Reinhard Zumkeller_, Nov 10 2013
%Y A106432 Cf. A000079.
%K A106432 nonn,base
%O A106432 0,4
%A A106432 _Reinhard Zumkeller_, Jan 22 2006
%E A106432 More terms from _Robert G. Wilson v_, Jan 25 2006