

A109811


Triangular numbers (A000217) at Levenshtein distance 1 from another triangular number when considered as a decimal string.


3



0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, 190, 210, 231, 253, 300, 378, 406, 435, 465
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

The Levenshtein distance (also called edit distance) between two strings is equal to the minimum number of insertion, deletion, or substitution operations needed to transform one string into the other. It is named after the Russian scientist Vladimir Levenshtein, who developed this metric in 1965. Levenshtein distance is a generalization of Hamming distance. The first tricky case here is the triangular number 171, as it is at least 2 operations away from any other 3digit 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.


REFERENCES

V. I. Levenshtein, Efficient reconstruction of sequences from their subsequences or supersequences, J. Combin. Theory Ser. A 93 (2001), no. 2, 310332.


LINKS

Table of n, a(n) for n=1..28.
Michael Gilleland, Levenshtein Distance, in Three Flavors. [It has been suggested that this algorithm gives incorrect results sometimes.  N. J. A. Sloane]


FORMULA

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.


EXAMPLE

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


CROSSREFS

Cf. A000040, A000217, A081355, A081356, A081230.
Sequence in context: A000217 A105340 A176659 * A025747 A025738 A078256
Adjacent sequences: A109808 A109809 A109810 * A109812 A109813 A109814


KEYWORD

base,nonn


AUTHOR

Jonathan Vos Post, Aug 16 2005


STATUS

approved



