cp's OEIS Frontend

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

%I A109809 #18 Dec 01 2018 07:59:52
%S A109809 2,3,11,223,1009,22111,100003,2211127,10000019,221111257,1000000009,
%T A109809 22111111123,100000000019,2211111111227,10000000000051,
%U A109809 221111111111197,1000000000000223,22111111111111117,100000000000000003,2211111111111111211,10000000000000000087,221111111111111111249
%N A109809 Primes at Levenshtein distance n from previous value when considered as a decimal string.
%C A109809 For positive n, the string length of a(n+1) is always the 1 + the string length of a(n). This sequence is infinite.
%H A109809 Vincenzo Librandi, <a href="/A109809/b109809.txt">Table of n, a(n) for n = 1..200</a>
%H A109809 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 A109809 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 A109809 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.
%e A109809 a(1) = 3 because we transform a(0) = 2 to 3 (a prime) with one substitution.
%e A109809 a(2) = 11 because we transform a(1) = 3 to the least prime 11 with 1 substitution plus one insertion.
%e A109809 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.
%t A109809 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]] ]];
%t A109809 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 *)
%Y A109809 Cf. A000040, A081355, A081356, A081230.
%K A109809 base,nonn
%O A109809 1,1
%A A109809 _Jonathan Vos Post_, Aug 16 2005
%E A109809 Corrected and extended by _Robert G. Wilson v_, Jan 25 2006