# Find the largest recurring prime

Inspired by Find the largest fragile prime

A recurring prime (or whatever you choose to call it) is a prime that, when removing leading digits, always remain prime regardless of how many digits are removed.

for example
6317 is a recurring prime because...
317 is a recurring prime because...
17 is a recurring prime because...
7 is a prime


727 is a prime but not a recurring prime because 27 is not a prime.

Goal
Like the original question, your score is the largest recurring prime found by your program/ algorithm.

Rules
I copied these from the original question

You may use any language and any third-party libraries.
You may use probabilistic primality tests.
Everything is in base 10.


Edit: Welp... turns out I have not factored in adding zeros in this question. Although I have not thought about adding 0 at first but it indeed satisfy my requirements, since removing a digit in front of (any number of) zeros skips many digits of prime tests and returns trivially true if the last few digits is a recurring prime. To make this question less of a "zero spam" but also reward strategic use of zeros, at most 2 consecutive zeros can be present in your answer. (Sorry to Level River St who asked me this)

• Are numbers where some digits are zero allowed? See my answer. Feb 16 '20 at 12:29
• @a'_' I think the point is that primes with multiple consecutive zeros are fairly trivial to find and not very interesting. For example I found 9000000000000007 manually. I have since deleted my answer. Feb 16 '20 at 13:02
• Not that Python is my first language, but that username... Feb 16 '20 at 17:15
• Just for interest (and because ovs seems to have found the largest prime admissible under the rules as they stand), I checked numbers of the form A*10**B+C where A and C are in the range 1..9 and B<1000 and found that 1E999+7 is the largest such prime in this range. Feb 17 '20 at 2:12
• @LuisMendo And the winning answer is in Python ...
– user92069
Feb 17 '20 at 6:41

# Python 3, 79 digits (probably optimal)

A simple depth first search that allows up to two consecutive zeros.

from sympy.ntheory.primetest import isprime

def dfs(n=0, k=1):
yield n
if 100*n > k:
yield from dfs(n, k*10)
for i in range(1,10):
if isprime(k*i + n):
yield from dfs(k*i + n, k*10)

l = 1
for prime in dfs():
if prime > l:
d = len(str(prime))
print(f'{d} digits: {prime}')
l = 10**d


Finds 200400201909005006060042636079002004200130030090050030780060900408062003 (72 digits) in 8 seconds on TIO. I let the program run on my computer a little longer and the highest recurrent prime it found is 7030560306007020600400306654060053003909007054300609009069003056030702030330347 (validation). The program actually completed after finding this number, so this is probably the longest prime meeting the challenges requirement.

Note that sympys isprime could theoretically return true for pseudoprimes >2^64, though no examples are known as of now.

# Python 3, 24 digits

only considers numbers without zeros

from sympy.ntheory.primetest import isprime

def dfs(n=0, k=1):
yield n
for i in range(1,10):
if isprime(k*i + n):
yield from dfs(k*i + n, k*10)

l = 1
for prime in dfs():
if prime > l:
print(f'{len(str(prime))} digits: {prime}')
l *= 10


Finds 357686312646216567629137 in less then a second on TIO.

• Your 24-digit prime without zeros is indeed known to be the biggest possible such answer: oeis.org/A024785
– xnor
Feb 16 '20 at 13:56
• If the search halts and there are no bugs in your code, that could be considered a proof that it's actually optimal. Feb 17 '20 at 2:20
• Made an iterative version Try it online! Feb 17 '20 at 9:05
• @mypronounismonicareinstate I guess so, but I'm not sure how interesting this find is outside of this challenge.
– ovs
Feb 17 '20 at 9:55

# Charcoal, 32 bytes

Ｆ37⊞υιＦυＦＥ⁹⁺⊕κι¿⬤…²Ｉκ﹪Ｉκλ«κＤ⎚


Try it online! Finds all zero-free recurring primes, but is inefficient, so the TIO link is limited to just under 60 seconds' worth of primes. Explanation:

Ｆ37⊞υι


Start with the two possible last digits of all recurring primes (except the trivial 2 and 5).

Ｆυ


Perform a breadth first search of recurring primes as they are found.

ＦＥ⁹⁺⊕κι


Prefix each non-zero digit to the prime so far.

¿⬤…²Ｉκ﹪Ｉκλ«


Use trial division to find out whether this is a new prime.

κＤ⎚⊞υκ


If it is then output it and add it to the list of recurring primes.