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

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

Author

Reinhard Zumkeller, Sep 16 2015

Keywords

• nonn
• base

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.

Examples

			.     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 .
		

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
• Eric Weisstein's World of Mathematics, Palindromic Number
• WikiBooks: Algorithm Implementation, Levenshtein Distance
• Wikipedia, Levenshtein Distance
• Wikipedia, Palindromic number
• Index entries for sequences related to palindromes

Crossrefs

Cf. A261423, A002113, A136522, A055642.

Programs

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