%I #13 Dec 01 2018 08:00:01
%S 0,1,3,6,10,15,21,28,36,45,55,66,78,91,105,120,136,153,171,190,210,
%T 231,253,300,378,406,435,465
%N Triangular numbers (A000217) at Levenshtein distance 1 from another triangular number when considered as a decimal string.
%C The first tricky case here is the triangular number 171, as it is at least 2 operations away from any other 3-digit triangular number. 276 might be the first triangular number not in this sequence, then 325, 351, 496. It would be interesting to generate the complement of this sequence: triangular numbers which are at least Levenstein distance 2 from any other triangular number.
%H Michael Gilleland, <a href="https://people.cs.pitt.edu/~kirk/cs1501/Pruhs/Spring2006/assignments/editdistance/Levenshtein%20Distance.htm">Levenshtein Distance, in Three Flavors</a>. [It has been suggested that this algorithm gives incorrect results sometimes. - _N. J. A. Sloane_]
%H V. I. Levenshtein, <a href="https://doi.org/10.1006/jcta.2000.3081">Efficient reconstruction of sequences from their subsequences or supersequences</a>, J. Combin. Theory Ser. A 93 (2001), no. 2, 310-332.
%F a(n) is in this sequence iff a(n) is an element of A000217 and there exists another element T of A000217 such that LD(a(n), T) = 1, where LD(A, B) = Levenshtein distance from A to B as decimal strings.
%e 0,1,3,6 are in this sequence because each is a triangular number that can be transformed into one of the others by substitution of the single digit.
%e 10 and 15 are in this sequence because each is a triangular number that can be transformed into each other by substitution of the second digit.
%e 21 and 28 can be transformed into each other by substitution of the second digit. 36 and 66 can be transformed into each other by substitution of the first digit. 45 and 55 can be transformed into each other by substitution of the first digit. 66 is of Levenshtein distance 2 from all other 2-digit triangular numbers, but can be transformed into the triangular number 666 by inserting one digit. 78 can be transformed into the triangular number 378 by inserting one digit. 91 is a substitution away from 21, or an insertion away from 1. Next, 105 is an insertion away from 15. We have 120 and 190 differing by the third digit. 136 is an insertion from 36. One insertion turns 15 to 153. One insertion gets from 171 to 1711. One insertion gets from 190 to 990. One insertion gets from 21 to 231. One insertion gets from 253 to 5253. One insertion gets from 300 to 3003. One insertion gets from 78 to 378. One substitution of 2nd digit gets from 406 to 496. Insertion turns 45 to 435 or 465.
%Y Cf. A000040, A000217, A081355, A081356, A081230.
%K nonn,base,more
%O 1,3
%A _Jonathan Vos Post_, Aug 16 2005
|