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 código de golf , por lo que gana el programa con la menor cantidad de bytes.
fuente
lo w
esorld\n1
. La nueva línea no termina el átomoRespuestas:
Jalea ,
2623 bytesAdelante
Pruébalo en línea!
Palabras
Ñ
¶
p
9
¶
7ÆR2ĿV€$ÆPÐf$ÐĿFị@
Hacia atrás
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.
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.9p
en lugar dep9
devolver el producto cartesiano invertido.fuente
Python 2,
143139 bytesConsta de cinco partes:
I=1
a={2}…[~-n]
I=0
Entonces, la inversión es simplemente cambiar el valor de
I
.Explicación
La función
f
realiza una búsqueda recursiva de primos truncables a la izquierda (LTP) o primos truncables a la derecha (RTP), dependiendo del valor del globalI
. Estos valores se agregan al conjuntoa
. Luego,lambda n:sorted(a)[~-n]
devuelve eln
ené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
f
podrí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,
z
debería agregarse al conjuntoa
y deberíamos recurrirstr(z)
. El bit responsable del código es:Primero, deseamos ocuparnos del caso
z == 2
. ¡Lo hacemos simplemente esquivando aquí y codificando2
cuando definimos inicialmentea
! (EDITAR: Y no pasa nada dañino si también atrapamosz == 1
). Entonces podemos asumir esoz ≥ 3
ahora.He traducido algunas "y" en una comparación encadenada de cortocircuito: las tres primeras comparaciones tienen éxito antes
a.add(z)
yf(u)
se evalúan. Aquí están todos sus roles:Agradecimientos
u=[d+s,s+d][I]
→u=d[I:]+s+d*I
;z==2
→z<3
y el truco mod 91 ). ¡Gracias!fuente