Derecho y primos truncables tfeL

11

Un primo truncable a la derecha es un primo donde cada prefijo es primo (en la base 10). Un primo truncable a la izquierda es exactamente lo contrario, donde cada postfix es un primo (los primos que comienzan con 0 no están permitidos). Ambas secuencias son finitas (solo hay 83 truncables a la derecha, mientras que hay 4260 truncables a la izquierda).

Usted tiene que escribir un programa que acepte un único número como entrada, y produce el n º privilegiada-truncatable. Sin embargo, cuando el programa se lee hacia atrás dispuestas , se debe producir el n º dejó truncatable-prime.

Para organizar un programa al revés, dividimos el programa en palabras, luego invertimos el orden de las palabras. Una palabra puede constar de cualquier número de caracteres.

Por ejemplo, si el siguiente fue su programa:

hello world
1234567890

Todo lo siguiente se permitiría como posibles arreglos hacia atrás:

División en cada personaje:

0987654321
dlrow olleh

División en espacios en blanco:

1234567890
world hello

División arbitraria (tuberías agregadas para mayor claridad):

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

908723456orld
1lo whel

Al organizar su programa al revés, todo el espacio en blanco debe considerarse y revertirse, al igual que cualquier otro personaje.

Entradas de prueba directa:

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

Entradas de prueba hacia atrás:

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

Los programas deberían poder ejecutarse en un período de tiempo razonable (menos de un minuto)

Este es un , por lo que gana el programa con la menor cantidad de bytes.

Nathan Merrill
fuente
No. El átomo después lo wes orld\n1. La nueva línea no termina el átomo
Nathan Merrill
Ah gracias. Ya lo pillo. Eliminar mis dos comentarios anteriores para evitar confusiones
Luis Mendo

Respuestas:

6

Jalea , 26 23 bytes

Adelante

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

Pruébalo en línea!

Palabras

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

Hacia atrás

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

Pruébalo en línea!

Palabras

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

Cómo funciona

Todos los programas de Jelly consisten en enlaces (funciones de toma de Jelly), que están separados por avances de línea o pilcrows ( ). El último de ellos es el enlace principal ; se llama automáticamente cuando se ejecuta el programa.

El programa de avance funciona de la siguiente manera.

Ñ                   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.

El programa hacia atrás hace casi exactamente lo mismo; Solo hay dos diferencias.

  • El enlace principal es ahora Ñ, que simplemente llama al enlace debajo de él (envolviendo), es decir, el enlace principal del programa de reenvío.

  • 9pen lugar de p9devolver el producto cartesiano invertido.

Dennis
fuente
4

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

Consta de cinco partes:

  1. I=1
  2. Una nueva línea
  3. a={2}…[~-n]
  4. Una nueva línea
  5. I=0

Entonces, la inversión es simplemente cambiar el valor de I.

Explicación

La función frealiza una búsqueda recursiva de primos truncables a la izquierda (LTP) o primos truncables a la derecha (RTP), dependiendo del valor del global I. Estos valores se agregan al conjunto a. Luego, lambda n:sorted(a)[~-n]devuelve el nenésimo.

Definamos una hoja como un LTP, un RTP, algún dígito distinto de cero + un LTP, o un RTP + algún dígito distinto de cero. Estos son todos los valores que fpodrían querer verificar la primalidad.

Diseñé una prueba de pseudoprime Fermat que funciona para todas las hojas:

      

(63973 es un número de Carmichael ).

Si esta prueba devuelve verdadero, zdebería agregarse al conjunto ay deberíamos recurrir str(z). El bit responsable del código es:

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

Primero, deseamos ocuparnos del caso z == 2. ¡Lo hacemos simplemente esquivando aquí y codificando 2cuando definimos inicialmente a! (EDITAR: Y no pasa nada dañino si también atrapamos z == 1). Entonces podemos asumir eso z ≥ 3ahora.

He traducido algunas "y" en una comparación encadenada de cortocircuito: las tres primeras comparaciones tienen éxito antes a.add(z)y f(u)se evalúan. Aquí están todos sus roles:

  1. z%91>0codifica nuestra primera condición. (63973 es divisible por 91, que no es una hoja en sí, así que así es como lo reconocemos).
  2. 0<2siempre es cierto, pero el encadenamiento es más corto que and.
  3. 2==pow(2,z,z) codifica nuestra segunda condición.
  4. pow(2,z,z)>a.add(z)desencadena la adición, y siempre es cierto, ya que set.addlos rendimientos None, y los números enteros son siempre mayores que None.
  5. a.add(z)<f(u)desencadena la recursividad. Su valor de verdad no es importante.

Agradecimientos

  • Dennis guardó cuatro bytes ( u=[d+s,s+d][I]u=d[I:]+s+d*I; z==2z<3y el truco mod 91 ). ¡Gracias!
Lynn
fuente