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

0, 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, 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, 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

Offset

0,3

Comments

a(n) = minimal number of editing steps (delete, insert or substitute) to transform n_10 into n_2.

Links

Alois P. Heinz, Table of n, a(n) for n = 0..20000

Michael Gilleland, Levenshtein Distance [It has been suggested that this algorithm gives incorrect results sometimes. - N. J. A. Sloane]

Maple

a:= n-> StringTools[Levenshtein](""||n, ""||(convert(n, binary))):
seq(a(n), n=0..105);  # Alois P. Heinz, Oct 16 2025

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]]; Array[f, 105]

Prog

(Python)
from Levenshtein import distance as LD
def a(n): return LD(str(n), bin(n)[2:])
print([a(n) for n in range(106)]) # Michael S. Branicky, Oct 16 2025

Crossrefs

Cf. A000027, A007088, first occurrence: A115778.

Cf. A081355.

Sequence in context: A366664 A097747 A285717 * A340033 A316847 A072768

Adjacent sequences: A115774 A115775 A115776 * A115778 A115779 A115780

Keyword

base,nonn

Author

Robert G. Wilson v, Jan 26 2006

Extensions

a(0)=0 prepended by Alois P. Heinz, Oct 16 2025

Status

approved