Right and tfeL truncatable primes

Question

A right-truncatable prime is a prime where every prefix is a prime (in base 10). A left-truncatable prime is exactly the opposite, where every postfix is a prime (primes that start with 0 aren't allowed). Both of these sequences are finite (There are only 83 Right-truncatables, while there are 4260 Left-truncatables).

You need to write a program that accepts a single number as input, and produces the nth right-truncatable prime. However, when the program is read arranged backwards, it should produce the nth left-truncatable prime.

To arrange a program backwards, we split the program into words, then reverse the order of the words. A word can consist of any number of characters.

For example, if the following was your program:

hello world
1234567890

The following would all be allowed as possible backwards arrangements:

Splitting on each character:

0987654321
dlrow olleh

Splitting on whitespace:

1234567890
world hello

Splitting arbitrarily (pipes added for clarity):

hel|lo w|orld
1|23456|7|8|90

908723456orld
1lo whel

When arranging your program backwards, all whitespace must be considered and reversed, just like any other character.

Forward test inputs:

1:  2
2:  3
21: 379
60: 239933
83: 73939133

Backward test inputs:

1:    2
2:    3
39:   647
187:  29173
4260: 357686312646216567629137

Programs should be able to run in a reasonable amount of time (less than a minute)

This is a code-golf, so the program with the fewest bytes wins!

Answer 1

Jelly, 26 23 bytes

Forward

Ѷp9¶7ÆR2ĿV€$ÆPÐf$ÐĿFị@

Try it online!

Words

Ñ ¶ p 9 ¶ 7ÆR2ĿV€$ÆPÐf$ÐĿFị@

Backward

7ÆR2ĿV€$ÆPÐf$ÐĿFị@¶9p¶Ñ

Try it online!

Words

7ÆR2ĿV€$ÆPÐf$ÐĿFị@ ¶ 9 p ¶ Ñ

How it works

All Jelly programs consist of links (Jelly's take on functions), which are separated by linefeeds or pilcrows (¶). The last of them is the main link; it is called automatically when the program is run.

The forward program works as follows.

Ñ                   Helper link. Unused.


p9                  Helper link. Take the Cartesian product with [1, ..., 9].


7ÆR2ĿV€$ÆPÐf$ÐĿFị@  Main link. Argument: n

7ÆR                 Yield all primes up to 7.
             ÐĿ     
            $ÐĿ     Combine the two quicklinks to the left into a monadic chain,
                    and call it repeatedly until the results are no longer unique.
                    Return the array of all intermediate results.
       $              Combine the two links to the left into a monadic chain.
   2Ŀ               Call the helper link on line 2.
     Ṿ€                 Eval each array in the product. This casts to string
                        before evaluating, thus concatenating both numbers.
        ÆPÐf        Filter by primality; keep only primes.
               F    Flatten the resulting array.
                ị@  Retrieve the element at index n.

The backward program does almost exactly the same; there are only two differences.

• The main link is now Ñ, which simply calls the link below it (wrapping around), i.e., the main link of the forward program.

• 9p instead of p9 return the reversed Cartesian product.

Answer 2

Python 2, 143 139 bytes

I=1
a={2}
def f(s):
 for d in'123456789':u=d[I:]+s+d*I;z=int(u);z+=z<3;z%91>0<2==pow(2,z,z)>a.add(z)<f(u)
f('')
lambda n:sorted(a)[~-n]
I=0

Consists of five parts:

1. I=1
2. A newline
3. a={2}…[~-n]
4. A newline
5. I=0

So reversal is just flipping the value of I.

Explanation

The function f performs a recursive search for either left-truncatable primes (LTPs) or right-truncatable primes (RTPs), depending on the value of the global I. These values get added to the set a. Then, lambda n:sorted(a)[~-n] returns the n-th one.

Let’s define a leaf as either an LTP, an RTP, some non-zero digit + an LTP, or an RTP + some non-zero digit. These are all the values that f could ever want to check for primality.

I designed a Fermat pseudoprime test that works for all leaves:

      

(63973 is a Carmichael number.)

If this test returns true, then z should be added to the set a and we should recurse on str(z). The responsible bit of code is:

z+=z<3;z%91>0<2==pow(2,z,z)>a.add(z)<f(u)

First, we wish to deal with the case z == 2. We do so by simply dodging it here and hard-coding 2 when we initially define a! (EDIT: And nothing harmful happens if we also catch z == 1.) So we can assume that z ≥ 3 now.

I’ve translated some “and”s into a short-circuiting chained comparison: the first three comparisons have to succeed before a.add(z) and f(u) are ever evaluated. Here are all their roles:

1. z%91>0 encodes our first condition. (63973 is divisible by 91, which is not a leaf itself, so that’s how we recognize it.)
2. 0<2 is always true, but chaining is shorter than and.
3. 2==pow(2,z,z) encodes our second condition.
4. pow(2,z,z)>a.add(z) triggers the addition, and is always true, since set.add returns None, and integers are always greater than None.
5. a.add(z)<f(u) triggers the recursion. Its truth value is unimportant.

Acknowledgements

• Dennis saved four bytes (u=[d+s,s+d][I] → u=d[I:]+s+d*I; z==2 → z<3 and the mod 91 trick). Thanks!