A118757 - OEIS

%I #22 Sep 14 2018 05:00:32

%S 0,1,2,3,4,5,6,7,8,9,19,18,17,16,15,14,13,12,11,10,20,21,22,23,24,25,

%T 26,27,28,29,39,38,37,36,35,34,33,32,31,30,40,41,42,43,44,45,46,47,48,

%U 49,59,58,57,56,55,54,53,52,51,50,60,61,62,63,64,65,66,67,68,69,79,78,77

%N Permutation of the natural numbers such that the Levenshtein distance between decimal representations of successive terms is 1, and a(n+1) is the largest such m < a(n) if it exists, or else the smallest such m > a(n); a(0) = 0.

%C a(n) = A003100(n) for n <= 100, a(100) = A003100(100) = 190, but a(101) = 180, A003100(101) = 191.

%C A118763 is the lexicographically smallest permutation with LevenshteinDistance[Base10](a(n),a(n+1)) = 1. - _M. F. Hasler_, Sep 12 2018

%H R. Zumkeller, <a href="/A118757/b118757.txt">Table of n, a(n) for n = 0..30000</a>

%H Michael Gilleland, <a href="http://people.cs.pitt.edu/~kirk/cs1501/Pruhs/Fall2006/Assignments/editdistance/Levenshtein%20Distance.htm">Levenshtein Distance</a>, 2006. [Broken link fixed by _M. F. Hasler_, Sep 12 2018, cf A118763]

%H R. Zumkeller, <a href="/A118757/a118757.txt">Values of A118757 for n<=1200</a>

%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>

%F a(n+1) = if U(n) is empty then Min(V(n)) else Max(U(n)), where the sets U and V are defined as: U(m) = {x < a(m) : LD10(a(m),x) = 1 and a(k) <> x for 0 <= k < m}, V(m) = {x > a(m) | LD10(a(m),x) = 1 and a(k) <> x for 0 <= k < m} with LD10 = Levenshtein distance in decimal representations of natural numbers.

%F a(n) = A118758(n) (self-inverse) for n < 100.

%Y Cf. A118763.

%Y Iterated twice: A118759(n) := a(a(n)).

%Y Fixed points: A118761 = { n | n = a(n) }.

%Y Inverse: A118758.

%Y First difference: A118762(n) := a(n+1) - a(n).

%K nonn,base,look

%O 0,3

%A _Reinhard Zumkeller_, May 01 2006

%E Correct definition and other edits by _M. F. Hasler_, Sep 12 2018