login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Please make a donation to keep the OEIS running. In 2018 we replaced the server with a faster one, added 20000 new sequences, and reached 7000 citations (often saying "discovered thanks to the OEIS").
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A109809 Primes at Levenshtein distance n from previous value when considered as a decimal string. 4
2, 3, 11, 223, 1009, 22111, 100003, 2211127, 10000019, 221111257, 1000000009, 22111111123, 100000000019, 2211111111227, 10000000000051, 221111111111197, 1000000000000223, 22111111111111117, 100000000000000003, 2211111111111111211, 10000000000000000087, 221111111111111111249 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 15 22:53 EST 2018. Contains 318157 sequences. (Running on oeis4.)