Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.
%I #9 Sep 17 2015 04:42:25
%S 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,
%T 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,
%U 1,1,2,2,2,2,2,2,1,0,1,1,2,2,2,2,2,2
%N Minimal number of editing steps (delete, insert or substitute) to transform n in decimal representation into the largest palindrome <= n.
%C a(n) = Levenshtein distance between n and A261423(n);
%C 0 <= a(n) <= A055642(n);
%C a(A002113(n)) = 0; a(m) = 0 iff A136522(m) = 1.
%H Reinhard Zumkeller, <a href="/A262257/b262257.txt">Table of n, a(n) for n = 0..10000</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PalindromicNumber.html">Palindromic Number</a>
%H WikiBooks: Algorithm Implementation, <a href="http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance">Levenshtein Distance</a>
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Levenshtein_distance">Levenshtein Distance</a>
%H Wikipedia, <a href="http://www.wikipedia.org/wiki/Palindromic_number">Palindromic number</a>
%H <a href="/index/Pac#palindromes">Index entries for sequences related to palindromes</a>
%e . n | A261423(n) | a(n) n | A261423(n) | a(n)
%e . -----+------------+----- ------+------------+-------
%e . 100 | 99 | 3 1000 | 999 | 4
%e . 101 | 101 | 0 1001 | 1001 | 0
%e . 102 | 101 | 1 1002 | 1001 | 1
%e . 103 | 101 | 1 1003 | 1001 | 1
%e . 104 | 101 | 1 1004 | 1001 | 1
%e . 105 | 101 | 1 1005 | 1001 | 1
%e . 106 | 101 | 1 1006 | 1001 | 1
%e . 107 | 101 | 1 1007 | 1001 | 1
%e . 108 | 101 | 1 1008 | 1001 | 1
%e . 109 | 101 | 1 1009 | 1001 | 1
%e . 110 | 101 | 2 1010 | 1001 | 2
%e . 111 | 111 | 0 1011 | 1001 | 1
%e . 112 | 111 | 1 1012 | 1001 | 2
%e . 113 | 111 | 1 1013 | 1001 | 2
%e . 114 | 111 | 1 1014 | 1001 | 2
%e . 115 | 111 | 1 1015 | 1001 | 2
%e . 116 | 111 | 1 1016 | 1001 | 2
%e . 117 | 111 | 1 1017 | 1001 | 2
%e . 118 | 111 | 1 1018 | 1001 | 2
%e . 119 | 111 | 1 1019 | 1001 | 2
%e . 120 | 111 | 2 1020 | 1001 | 2
%e . 121 | 121 | 0 1021 | 1001 | 1
%e . 122 | 121 | 1 1022 | 1001 | 2
%e . 123 | 121 | 1 1023 | 1001 | 2
%e . 124 | 121 | 1 1024 | 1001 | 2
%e . 125 | 121 | 1 1025 | 1001 | 2 .
%o (Haskell)
%o import Data.Function (on); import Data.List (genericIndex)
%o a262257 n = genericIndex a262257_list n
%o a262257_list = zipWith (levenshtein `on` show) [0..] a261423_list where
%o levenshtein us vs = last $ foldl transform [0..length us] vs where
%o transform xs@(x:xs') c = scanl compute (x+1) (zip3 us xs xs') where
%o compute z (c', x, y) = minimum [y+1, z+1, x + fromEnum (c' /= c)]
%Y Cf. A261423, A002113, A136522, A055642.
%K nonn,base
%O 0,11
%A _Reinhard Zumkeller_, Sep 16 2015