cp's OEIS Frontend

A115777 Levenshtein distance between n considered as a decimal string and n considered as a binary string.

%I A115777 #6 Dec 01 2018 04:37:24
%S A115777 0,2,2,3,3,3,3,4,4,2,2,3,3,3,3,4,4,4,4,4,4,5,5,5,5,5,5,5,5,4,4,6,6,6,
%T A115777 6,6,6,6,6,5,5,6,6,6,6,6,6,6,6,5,5,6,6,6,6,6,6,6,6,5,5,6,6,7,7,7,7,7,
%U A115777 7,6,6,7,7,7,7,7,7,7,7,6,6,7,7,7,7,7,7,7,7,6,6,7,7,7,7,7,7,7,7,4,4,5,5,5,5
%N A115777 Levenshtein distance between n considered as a decimal string and n considered as a binary string.
%C A115777 a(n) = minimal number of editing steps (delete, insert or substitute) to transform n_10 into n_2.
%H A115777 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_]
%t A115777 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]]]];
%t A115777 f[n_] := levenshtein[ IntegerDigits[n], IntegerDigits[n, 2]]; Array[f, 105]
%Y A115777 Cf. A000027, A007088, first occurrence: A115778.
%K A115777 base,nonn
%O A115777 1,2
%A A115777 _Robert G. Wilson v_, Jan 26 2006