11
\$\begingroup\$

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 , so the program with the fewest bytes wins!

\$\endgroup\$
  • \$\begingroup\$ no. The atom after lo w is orld\n1. The newline doesn't end the atom \$\endgroup\$ – Nathan Merrill Aug 15 '16 at 16:49
  • \$\begingroup\$ Ah, thanks. Got it now. Removing my two previous comments to avoid confusion \$\endgroup\$ – Luis Mendo Aug 15 '16 at 16:50
6
\$\begingroup\$

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.

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

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==2z<3 and the mod 91 trick). Thanks!
\$\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.