cp's OEIS Frontend

A262257 Minimal number of editing steps (delete, insert or substitute) to transform n in decimal representation into the largest palindrome <= n.

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