8
\$\begingroup\$

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)

\$\endgroup\$
  • 1
    \$\begingroup\$ Are numbers where some digits are zero allowed? See my answer. \$\endgroup\$ – Level River St Feb 16 at 12:29
  • \$\begingroup\$ @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. \$\endgroup\$ – Level River St Feb 16 at 13:02
  • 6
    \$\begingroup\$ Not that Python is my first language, but that username... \$\endgroup\$ – Luis Mendo Feb 16 at 17:15
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Level River St Feb 17 at 2:12
  • 4
    \$\begingroup\$ @LuisMendo And the winning answer is in Python ... \$\endgroup\$ – user92069 Feb 17 at 6:41
7
\$\begingroup\$

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

Try it online! Validate the result!

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

Try it online! Validate the result!

Finds 357686312646216567629137 in less then a second on TIO.

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

Charcoal, 32 bytes

F37⊞υιFυFE⁹⁺⊕κι¿⬤…²Iκ﹪Iκλ«κD⎚

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:

F37⊞υι

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

Fυ

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

FE⁹⁺⊕κι

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

¿⬤…²Iκ﹪Iκλ«

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

κD⎚⊞υκ

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

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.