11
\$\begingroup\$

Heavily inspired by Programming a Pristine World. Also closely related to this challenge.


Let's define a pristine prime as a number which is itself prime, but will no longer be prime if you remove any contiguous substring of N base 10 digits, where 0 < N < digits in number.

For example, 409 is a pristine prime because 409 itself is prime, but all numbers resulting from removing a substring of 1 digit are not prime:

40
49
09 = 9

and all numbers resulting from removing substrings of length 2 are not prime:

4
9

On the other hand, the prime number 439 is not pristine. Removing the different substrings results in:

43
49
39
4
9

While 49, 39, 4, and 9 are all non-prime, 43 is prime; thus, 439 is not pristine.

2, 3, 5, and 7 are trivially pristine, since they cannot have any substrings removed.

Challenge

Your challenge is to create a program or function that takes in a positive integer N and outputs the Nth pristine prime. The code should finish in under 1 minute on any modern PC for any input up to 50.

The shortest code in bytes wins.

As a reference, here are the first 20 pristine primes:

N    Pristine prime
1    2
2    3
3    5
4    7
5    11
6    19
7    41
8    61
9    89
10   409
11   449
12   499
13   821
14   881
15   991
16   6299
17   6469
18   6869
19   6899
20   6949

Here is a full list of pristine primes up to 1e7, or N = 376.

Finally, here are two related OEIS entries:

  • A033274: very similar, but generated by keeping substrings instead of removing them.
  • A071062: oddly similar, but generated in a much different manner.
\$\endgroup\$
5
\$\begingroup\$

Pyth, 29 bytes

e.f>}ZPZsmq1lPs.D`Z}Fd.CU`Z2Q

Golfing, explanation, etc. to follow.

\$\endgroup\$
4
\$\begingroup\$

CJam, 51 bytes

1ri{{)_mp1$s_,)2m*{:>},\f{\~2$<@@>+0e|imp}1b!&!}g}*

Just a first pass, this can probably be improved a lot.

Test it here.

\$\endgroup\$
3
\$\begingroup\$

Japt, 61 bytes

$while(V<U)T$°,W=Ts ,Tj «Wl o d@1o1-X+Wl)dZ{WjYZ n j} } ©V°;T

Try it online!

It's a shame I haven't implemented loops in Japt yet, otherwise this would be a good bit shorter. Still golfing...

\$\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.