login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A115777 Levenshtein distance between n considered as a decimal string and n considered as a binary string. 4
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

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

LINKS

Table of n, a(n) for n=1..105.

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

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]

CROSSREFS

Cf. A000027, A007088, first occurrence: A115778.

Sequence in context: A235703 A097747 A285717 * A316847 A072768 A071673

Adjacent sequences:  A115774 A115775 A115776 * A115778 A115779 A115780

KEYWORD

base,nonn

AUTHOR

Robert G. Wilson v, Jan 26 2006

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 26 03:55 EDT 2020. Contains 337346 sequences. (Running on oeis4.)