|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,11
|
|
COMMENTS
|
a(n) = Levenshtein distance between n and A261423(n);
|
|
LINKS
|
|
|
EXAMPLE
|
. -----+------------+----- ------+------------+-------
. 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
|
|
|
STATUS
|
approved
|
|
|
|