login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A106432 Levenshtein distance between successive powers of 2 in decimal representation. 1
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

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

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 *)

PROG

(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

CROSSREFS

Cf. A000079.

Sequence in context: A132944 A210568 A262887 * A227923 A029836 A004257

Adjacent sequences:  A106429 A106430 A106431 * A106433 A106434 A106435

KEYWORD

nonn,base

AUTHOR

Reinhard Zumkeller, Jan 22 2006

EXTENSIONS

More terms from Robert G. Wilson v, Jan 25 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 March 21 22:19 EDT 2019. Contains 321382 sequences. (Running on oeis4.)