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

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

Offset

1,1

Comments

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

Links

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.

Formula

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.

Example

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.

Mathematica

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 *)

Crossrefs

Cf. A000040, A081355, A081356, A081230.

Sequence in context: A066100 A029497 A318130 * A211349 A096456 A262201

Adjacent sequences: A109806 A109807 A109808 * A109810 A109811 A109812

Keyword

base,nonn

Author

Jonathan Vos Post, Aug 16 2005

Extensions

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

Status

approved