cp's OEIS Frontend

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

%I A118757 #22 Sep 14 2018 05:00:32
%S A118757 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 A118757 26,27,28,29,39,38,37,36,35,34,33,32,31,30,40,41,42,43,44,45,46,47,48,
%U A118757 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 A118757 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 A118757 a(n) = A003100(n) for n <= 100, a(100) = A003100(100) = 190, but a(101) = 180, A003100(101) = 191.
%C A118757 A118763 is the lexicographically smallest permutation with LevenshteinDistance[Base10](a(n),a(n+1)) = 1. - _M. F. Hasler_, Sep 12 2018
%H A118757 R. Zumkeller, <a href="/A118757/b118757.txt">Table of n, a(n) for n = 0..30000</a>
%H A118757 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 A118757 R. Zumkeller, <a href="/A118757/a118757.txt">Values of A118757 for n<=1200</a>
%H A118757 <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%F A118757 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 A118757 a(n) = A118758(n) (self-inverse) for n < 100.
%Y A118757 Cf. A118763.
%Y A118757 Iterated twice: A118759(n) := a(a(n)).
%Y A118757 Fixed points: A118761 = { n | n = a(n) }.
%Y A118757 Inverse: A118758.
%Y A118757 First difference: A118762(n) := a(n+1) - a(n).
%K A118757 nonn,base,look
%O A118757 0,3
%A A118757 _Reinhard Zumkeller_, May 01 2006
%E A118757 Correct definition and other edits by _M. F. Hasler_, Sep 12 2018