A081355 -id:A081355 - cp's OEIS frontend

A081356 Least m such that A081355(m)=LD(m,m^2)=n, where LD(x,y) denotes the Levenshtein distance between x and y in decimal representation.

0, 2, 4, 17, 33, 144, 317, 1439, 3167, 14144, 31624, 141442, 316229, 1414234, 3162922, 14142148, 31622888, 141422444, 316292397, 1414213838, 3162353552, 14142137977, 31622912229, 141421462429, 316228884988, 1414214626248

Offset: 0

Reinhard Zumkeller, Mar 18 2003

			a(4)=33, as A081355(33)=LD(33,33^2)=LD(33,1089)=4 and A081355(m)<4 for m<=33.

Michael Gilleland, Levenshtein Distance. [It has been suggested that this algorithm gives incorrect results sometimes. - _N. J. A. Sloane_]

More terms from David Wasserman, Jun 01 2004

A109809 Primes at Levenshtein distance n from previous value when considered as a decimal string.

Original entry on oeis.org

2, 3, 11, 223, 1009, 22111, 100003, 2211127, 10000019, 221111257, 1000000009, 22111111123, 100000000019, 2211111111227, 10000000000051, 221111111111197, 1000000000000223, 22111111111111117, 100000000000000003, 2211111111111111211, 10000000000000000087, 221111111111111111249

Offset: 1

Jonathan Vos Post, Aug 16 2005

For positive n, the string length of a(n+1) is always the 1 + the string length of a(n). This sequence is infinite.

			a(1) = 3 because we transform a(0) = 2 to 3 (a prime) with one substitution.
a(2) = 11 because we transform a(1) = 3 to the least prime 11 with 1 substitution plus one insertion.
a(3) = 223 because we transform a(2) = 11 to the prime 223 with 2 substitutions plus one insertion and any smaller prime can be transformed from 11 in fewer than 3 steps.

Vincenzo Librandi, Table of n, a(n) for n = 1..200
Michael Gilleland, Levenshtein Distance, in Three Flavors. [It has been suggested that this algorithm gives incorrect results sometimes. - _N. J. A. Sloane_]
V. I. Levenshtein, Efficient reconstruction of sequences from their subsequences or supersequences, J. Combin. Theory Ser. A 93 (2001), no. 2, 310-332.

Cf. A000040, A081355, A081356, A081230.

levenshtein[s_List, t_List] := Module[{d, n = Length@s, m = Length@t}, Which[s === t, 0, n == 0, m, m == 0, n, s != t, d = Table[0, {m + 1}, {n + 1}]; d[[1, Range[n + 1]]] = Range[0, n]; d[[Range[m + 1], 1]] = Range[0, m]; Do[ d[[j + 1, i + 1]] = Min[d[[j, i + 1]] + 1, d[[j + 1, i]] + 1, d[[j, i]] + If[ s[[i]] === t[[j]], 0, 1]], {j, m}, {i, n}]; d[[ -1, -1]] ]];
NextPrim[n_] := Block[{k = n + 1}, While[ !PrimeQ@k, k++ ]; k]; a[0] = 2; a[n_] := a[n] = Block[{q = IntegerDigits[a[n - 1]][[1]], id = IntegerDigits@a[n - 1]}, p = NextPrim[ If[q == 1, Floor[199*10^(n - 1)/90 - 1], 10^(n - 1)]]; While[ levenshtein[id, IntegerDigits@p] != n, p = NextPrim@p]; p]; Table[ a[n], {n, 0, 19}] (* Robert G. Wilson v, Jan 25 2006 *)

a(0) = 2, a(n+1) = least prime p such that LD(a(n), p) = n, where LD(A,B) = Levenshtein distance from A to B as decimal strings.

Corrected and extended by Robert G. Wilson v, Jan 25 2006

A109382 Levenshtein distance between successive English names of nonnegative integers, excluding spaces and hyphens.

Original entry on oeis.org

4, 3, 4, 5, 3, 3, 4, 5, 4, 3, 4, 4, 6, 3, 3, 2, 4, 4, 3, 7, 3, 3, 4, 5, 3, 3, 4, 5, 4, 7, 3, 3, 4, 5, 3, 3, 4, 5, 4, 7, 3, 3, 4, 5, 3, 3, 4, 5, 4, 6, 3, 3, 4, 5, 3, 3, 4, 5, 4, 6, 3, 3, 4, 5, 3, 3, 4, 5, 4, 7, 3, 3, 4, 5, 3, 3, 4, 5, 4, 8, 3, 3, 4, 5, 3, 3, 4, 5, 4, 7, 3, 3, 4, 5, 3, 3, 4, 5, 4, 7, 3, 3, 4, 5, 3, 3

Offset: 0

Jonathan Vos Post, Aug 25 2005

			a(0) = 4 since LD(ZERO,ONE) requires 4 edits.
a(1) = 3 since LD(ONE,TWO) which requires 3 substitutions.
a(2) = 4 since LD(TWO,THREE) = requires 4 edits (leave the leftmost T unchanged), then 2 substitutions (W to H, O to R), then 2 insertions (E,E).
a(4) = 3 as LD(FOUR,FIVE) leaves the leftmost F unchanged, then requires 3 substitutions. From FIVE to SIX leaves the I unchanged. From SIX to SEVEN leaves the S unchanged. From TEN to ELEVEN leaves the EN unchanged. From ELEVEN to TWELVE leaves an E,L,V,E unchanged. From THIRTEEN to FOURTEEN leaves RTEEN unchanged. TWENTYNINE to THIRTY takes 7 edits. THIRTYNINE to FORTY takes 7 edits. SEVENTYNINE to EIGHTY takes 8 edits. EIGHTYNINE to NINETY takes 7 edits. NINETYNINE to ONEHUNDRED takes 7 edits.

Robert Israel, Table of n, a(n) for n = 0..10000
Michael Gilleland, Levenshtein Distance, in Three Flavors.
V. I. Levenshtein, Efficient reconstruction of sequences from their subsequences or supersequences, J. Combin. Theory Ser. A 93 (2001), no. 2, 310-332.
Landon Curt Noll, The English Name of a Number.
Robert G. Wilson v, American English names for the numbers from 0 to 100999 without spaces or hyphens.

Cf. A001477, A005589, A081355, A081356, A081230, A109809, A109811.

with(StringTools):
seq(Levenshtein(Select(IsAlpha, convert(n,english)),Select(IsAlpha,convert(n+1,english))),n=0..200); # Robert Israel, Jan 23 2018

(* First copy b109382.txt out of A109382 then *) levenshtein[s_List, t_List] := Module[{d, n = Length@s, m = Length@t}, Which[s === t, 0, n == 0, m, m == 0, n, s != t, d = Table[0, {m + 1}, {n + 1}]; d[[1, Range[n + 1]]] = Range[0, n]; d[[Range[m + 1], 1]] = Range[0, m]; Do[ d[[j + 1, i + 1]] = Min[d[[j, i + 1]] + 1, d[[j + 1, i]] + 1, d[[j, i]] + If[ s[[i]] === t[[j]], 0, 1]], {j, m}, {i, n}]; d[[ -1, -1]] ]]; f[x_] := Block[{str = ToString@ lst[[x]], len}, len = StringLength@ str; StringInsert[str, ",", Range[2, len]]]

a(n) = LD(nameof(n), nameof(n+1)).

More terms from Robert G. Wilson v, Jan 31 2006

Corrected by Robert Israel, Jan 23 2018

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

Original entry on oeis.org

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, 496, 528, 561, 595, 666, 703, 741, 780, 820, 861, 903, 990, 1035, 1081, 1128, 1176, 1225, 1275, 1326, 1378, 1485, 1540, 1653, 1711, 1891

Offset: 1

Jonathan Vos Post, Aug 16 2005

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.

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

Michael Gilleland, Levenshtein Distance, in Three Flavors. [It has been suggested that this algorithm gives incorrect results sometimes. - _N. J. A. Sloane_]
V. I. Levenshtein, Efficient reconstruction of sequences from their subsequences or supersequences, J. Combin. Theory Ser. A 93 (2001), no. 2, 310-332.

Cf. A000217, A081355, A081356, A081230.

nd = 5
t = [n*(n+1)//2 for n in range(int((2*10**nd)**.5))]
a = set()
dig = [''] + list('0123456789')
for x in t:
    s = str(x)
    for i in range(len(s)):
        for c in dig:
            if (i, c) == (0, '') and len(s) > 1 and s[1] == '0': continue
            r = s[:i] + c + s[i+1:]
            if r != s and r and int(r) in t:
                a.add(int(r))
                a.add(x)
a = list(sorted(x for x in a if x < 10**(nd-1)))
print(a) # Andrey Zabolotskiy, Oct 05 2024

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.

Terms a(29) and beyond added by Andrey Zabolotskiy, Oct 05 2024

A109378 Semiprimes at Levenshtein distance n from previous value when considered as a decimal string.

Original entry on oeis.org

4, 6, 10, 221, 1003, 22226, 100001, 2222245, 10000001, 222222223, 1000000006, 2222222227, 100000000013, 2222222222249, 10000000000015, 222222222222223, 10000000000000031, 22222222222222229, 100000000000000015

Offset: 0

Jonathan Vos Post, Aug 25 2005

For positive n, the string length of a(n+1) is always the 1 + the string length of a(n). This sequence is infinite.

			a(0) = 4 = 2^2.
a(1) = 6 because we transform a(0) = 4 to 6 = 2 * 3 (a semiprime) with one substitution.
a(2) = 10 because we transform a(1) = 6 to 10 = 2 * 5 with one substitution and one insertion.
a(3) = 221 because we transform a(2) = 10 to the least semiprime 221 = 13 * 17 with 1 substitution plus two insertion.
a(4) = 1003 because we transform a(3) = 221 to the least semiprime 1003 = 17 * 59 with 3 substitutions plus one insertion and any smaller semiprime can be transformed from 221 in fewer than 4 steps.
a(20) = 10000000000000000001 = 11 * 909090909090909091, which is the least semiprime of Levenshtein distance 20 from a(19) = 2222222222222222222 from which decimal string we transform to a(20) with 19 substitutions and one insertion.

Michael Gilleland, Levenshtein Distance, in Three Flavors. [It has been suggested that this algorithm gives incorrect results sometimes. - _N. J. A. Sloane_]
V. I. Levenshtein, Efficient reconstruction of sequences from their subsequences or supersequences, J. Combin. Theory Ser. A 93 (2001), no. 2, 310-332.

Cf. A001358, A081355, A081356, A081230, A109809, A109811.

A109380 Levenshtein distance between successive factorials when considered as decimal strings.

Original entry on oeis.org

0, 1, 1, 2, 2, 1, 3, 3, 5, 1, 4, 5, 7, 7, 9, 9, 10, 12, 13, 14, 12, 12, 16, 15, 17, 16, 19, 16, 21, 24, 21, 22, 22, 25, 25, 25, 27, 32, 33, 30, 34, 34, 36, 36, 37, 38, 38, 44, 42, 44, 42, 46, 47, 48, 50, 50, 47, 52, 52, 49, 54, 60, 60, 59, 56, 60, 62, 68, 70, 65, 65, 67, 70, 70, 74

Offset: 0

Jonathan Vos Post, Aug 25 2005

			a(0) = 0 since LD(0!,1!) = LD(1,1) which requires 0 edits.
a(1) = 1 since LD(1!,2!) = LD(1,2) which requires 1 substitution.
a(2) = 1 since LD(2!,3!) = LD(2,6) which requires 1 substitution.
a(3) = 2 since LD(3!,4!) = LD(6,24) which requires 1 substitution and 1 insertion.
a(4) = 2 since LD(4!,5!) = LD(24,120) which requires 1 insertion (1 to the left of 2) and 1 substitution (from 4 to 0).
a(5) = 1 since LD(5!,6!) = LD(120,720) which requires 1 substitution (from 1 to 7).
a(6) = 3 since LD(6!,7!) = LD(720,5040) which requires 1 substitution (from 7 to 5), then 2 insertions (0 to right of 7, 4 to right of 7) and leaving the rightmost digit unedited.
a(7) = 3 as it takes a minimum of 3 edits to get from 5040 to 40320.
a(8) = 5 since LD(8!,9!) = LD(40320,362880) which requires 5 edits.
a(9) = 1 since LD(9!,10!) = LD(362880,3628800) which requires 1 insertion of a zero.
a(10) = 4 since LD(10!,11!) = LD(3628800,39916800) which takes 4 edits.

Michael Gilleland, Levenshtein Distance, in Three Flavors. [It has been suggested that this algorithm gives incorrect results sometimes. - _N. J. A. Sloane_]
V. I. Levenshtein, Efficient reconstruction of sequences from their subsequences or supersequences, J. Combin. Theory Ser. A 93 (2001), no. 2, 310-332.

Cf. A001358, A081355, A081356, A081230, A109809, A109811.

levenshtein[s_List, t_List] := Module[{d, n = Length@s, m = Length@t}, Which[s === t, 0, n == 0, m, m == 0, n, s != t, d = Table[0, {m + 1}, {n + 1}]; d[[1, Range[n + 1]]] = Range[0, n]; d[[Range[m + 1], 1]] = Range[0, m]; Do[ d[[j + 1, i + 1]] = Min[d[[j, i + 1]] + 1, d[[j + 1, i]] + 1, d[[j, i]] + If[ s[[i]] === t[[j]], 0, 1]], {j, m}, {i, n}]; d[[ -1, -1]] ]];
f[n_] := levenshtein[IntegerDigits[n! ], IntegerDigits[(n + 1)! ]]; Table[ f[n], {n, 0, 74}] (* Robert G. Wilson v *)

a(n) = LD(n!,(n+1)!).

Corrected and extended by Robert G. Wilson v, Jan 25 2006

cp's OEIS Frontend

A081356 Least m such that A081355(m)=LD(m,m^2)=n, where LD(x,y) denotes the Levenshtein distance between x and y in decimal representation.

Views

Author

Keywords

Examples

Links

Extensions

A109809 Primes at Levenshtein distance n from previous value when considered as a decimal string.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A109382 Levenshtein distance between successive English names of nonnegative integers, excluding spaces and hyphens.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Formula

Extensions

A109378 Semiprimes at Levenshtein distance n from previous value when considered as a decimal string.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A109380 Levenshtein distance between successive factorials when considered as decimal strings.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions