cp's OEIS Frontend

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

%I A109811 #20 Oct 06 2024 09:45:13
%S A109811 0,1,3,6,10,15,21,28,36,45,55,66,78,91,105,120,136,153,171,190,210,
%T A109811 231,253,300,378,406,435,465,496,528,561,595,666,703,741,780,820,861,
%U A109811 903,990,1035,1081,1128,1176,1225,1275,1326,1378,1485,1540,1653,1711,1891
%N A109811 Triangular numbers (A000217) at Levenshtein distance 1 from another triangular number when considered as a decimal string.
%C A109811 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 is the first triangular number not in this sequence, then 325, 351, 630. It would be interesting to generate the complement of this sequence: triangular numbers which are at least Levenshtein distance 2 from any other triangular number.
%H A109811 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 A109811 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 A109811 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 A109811 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 A109811 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 A109811 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 second digit. 136 is an insertion from 36. One insertion turns 15 to 153. One insertion gets from 171 to 1711. One substitution 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.
%o A109811 (Python)
%o A109811 nd = 5
%o A109811 t = [n*(n+1)//2 for n in range(int((2*10**nd)**.5))]
%o A109811 a = set()
%o A109811 dig = [''] + list('0123456789')
%o A109811 for x in t:
%o A109811     s = str(x)
%o A109811     for i in range(len(s)):
%o A109811         for c in dig:
%o A109811             if (i, c) == (0, '') and len(s) > 1 and s[1] == '0': continue
%o A109811             r = s[:i] + c + s[i+1:]
%o A109811             if r != s and r and int(r) in t:
%o A109811                 a.add(int(r))
%o A109811                 a.add(x)
%o A109811 a = list(sorted(x for x in a if x < 10**(nd-1)))
%o A109811 print(a) # _Andrey Zabolotskiy_, Oct 05 2024
%Y A109811 Cf. A000217, A081355, A081356, A081230.
%K A109811 nonn,base
%O A109811 1,3
%A A109811 _Jonathan Vos Post_, Aug 16 2005
%E A109811 Terms a(29) and beyond added by _Andrey Zabolotskiy_, Oct 05 2024