login
A262257
Minimal number of editing steps (delete, insert or substitute) to transform n in decimal representation into the largest palindrome <= n.
2
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 0, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 0, 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 1, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2, 1, 0, 1, 1, 1, 2, 2, 2, 2, 2, 2, 1, 0, 1, 1, 2, 2, 2, 2, 2, 2
OFFSET
0,11
COMMENTS
a(n) = Levenshtein distance between n and A261423(n);
0 <= a(n) <= A055642(n);
a(A002113(n)) = 0; a(m) = 0 iff A136522(m) = 1.
LINKS
Eric Weisstein's World of Mathematics, Palindromic Number
WikiBooks: Algorithm Implementation, Levenshtein Distance
EXAMPLE
. n | A261423(n) | a(n) n | A261423(n) | a(n)
. -----+------------+----- ------+------------+-------
. 100 | 99 | 3 1000 | 999 | 4
. 101 | 101 | 0 1001 | 1001 | 0
. 102 | 101 | 1 1002 | 1001 | 1
. 103 | 101 | 1 1003 | 1001 | 1
. 104 | 101 | 1 1004 | 1001 | 1
. 105 | 101 | 1 1005 | 1001 | 1
. 106 | 101 | 1 1006 | 1001 | 1
. 107 | 101 | 1 1007 | 1001 | 1
. 108 | 101 | 1 1008 | 1001 | 1
. 109 | 101 | 1 1009 | 1001 | 1
. 110 | 101 | 2 1010 | 1001 | 2
. 111 | 111 | 0 1011 | 1001 | 1
. 112 | 111 | 1 1012 | 1001 | 2
. 113 | 111 | 1 1013 | 1001 | 2
. 114 | 111 | 1 1014 | 1001 | 2
. 115 | 111 | 1 1015 | 1001 | 2
. 116 | 111 | 1 1016 | 1001 | 2
. 117 | 111 | 1 1017 | 1001 | 2
. 118 | 111 | 1 1018 | 1001 | 2
. 119 | 111 | 1 1019 | 1001 | 2
. 120 | 111 | 2 1020 | 1001 | 2
. 121 | 121 | 0 1021 | 1001 | 1
. 122 | 121 | 1 1022 | 1001 | 2
. 123 | 121 | 1 1023 | 1001 | 2
. 124 | 121 | 1 1024 | 1001 | 2
. 125 | 121 | 1 1025 | 1001 | 2 .
PROG
(Haskell)
import Data.Function (on); import Data.List (genericIndex)
a262257 n = genericIndex a262257_list n
a262257_list = zipWith (levenshtein `on` show) [0..] a261423_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)]
CROSSREFS
KEYWORD
nonn,base
AUTHOR
Reinhard Zumkeller, Sep 16 2015
STATUS
approved