Secuencia aritmética de primes del bibliotecario loco

18

Bueno, el bibliotecario lo atrapó haciendo trampa en su trabajo usando su algoritmo de clasificación , por lo que ahora está siendo castigado. Se le ha ordenado que cree un código para que el bibliotecario pueda impresionar el objeto de su afecto no correspondido, el profesor de matemáticas. Entonces eso es lo que significa "Otros deberes asignados" ...

Todos están familiarizados con la secuencia numérica natural en la base 10, llamada N :

0, 1, 2, 3, 4, 5, 6, ...

A partir de eso, podemos generar la secuencia de números primos, llamémosla P , de modo que cada elemento en P tenga exactamente dos divisores en N , a saber, 1y en sí mismo. Esta secuencia es:

2, 3, 5, 7, 11, 13, ...

OK, bastante rutina hasta ahora.

El bibliotecario pensó en una ingeniosa función F (x, y) que toma un número xde N , con la condición 0 <= x <= 9, y un número yde N , y se inserta xen yla expansión decimal de cada posición (es decir, anteponer, insertar o agregar xa y), luego devuelve el conjunto ordenado de nuevos números.
Por ejemplo, F (6, 127) daría como resultado

1267, 1276, 1627, 6127

Sin embargo, todavía es un poco aburrido. Los deseos bibliotecario para condimentar las cosas un poco más por el lugar que especifica una nueva función z -> {p : p in P and F(z,p) subset of P}, ordenados ascendente.
Por ejemplo, z (7) sería

3, 19, 97, 433, 487, 541, ...

porque 37y 73son primos, 719 179y 197son primos, etc.

Tenga en cuenta que z (2) está vacío, porque ningún primo que tenga un 2anexo seguirá siendo primo. Del mismo modo para {0,4,5,6,8}.

Su tarea es escribir código que generará y generará los primeros 100 números en la secuencia z (x) para una x dada .

Entrada

Un solo entero x tal que 0 <= x <= 9. La entrada puede ser a través del argumento de función, STDIN o equivalente.

Salida

Una secuencia de los primeros 100 números, delimitada por su elección, a STDOUT o equivalente, de modo que la secuencia satisfaga z (x) como se describió anteriormente. Si z (x) está vacío, como es el caso de {0,2,4,5,6,8}, las palabras Empty Setdeberían salir en su lugar.

Restricciones

  • Este es el código de golf, ya que necesitará transcribirlo a una tarjeta de índice para que el bibliotecario pueda mostrarle al maestro de matemáticas, y su mano tenga calambres fácilmente.
  • Se aplican restricciones de escapatoria estándar. El bibliotecario no tolera a los tramposos.

Secuencias de referencia

x = 1: A069246
x = 3: A215419
x = 7: A215420
x = 9: A215421

Relacionado: Encuentra el primo frágil más grande / Encuentra el primo más pequeño de una subcadena / Encuentra el primo más grande que sigue siendo un primo después de la eliminación de dígitos

AdmBorkBork
fuente

Respuestas:

5

Pyth, 49 bytes

Al igual que Python3 y otras respuestas de Pyth, el tiempo de ejecución para encontrar 100 números es prohibitivo. (conjunto de pruebas da 10)

?}z"1379".f&!tPZ!|FmtPvjzc`Z]dhl`Z*TT3"Empty Set"

Pruébalo en línea

Brian Tuck
fuente
1
El seguimiento "es innecesario, aunque es un trabajo muy agradable.
FryAmTheEggman
Gracias por el recordatorio. Debido a que EOL ya no termina una cadena, he evitado cadenas sin terminar, pero, por supuesto, EOF todavía funciona
Brian Tuck,
4

Python 3, 188 bytes

x=input()
k=1
i=100
if x in"024568":i=print("Empty Set")
while i:k+=1;s=str(k);i-=all(sum(p%d<1for d in range(2,p))<4for p in[k*int(s[:j]+x+s[j:])for j in range(len(s)+1)])and not print(k)

Mal golf, pero aquí hay algo por ahora. En lugar de verificar p in P and F(z,p) subset of P, verificamos que p*fsea ​​un semiprime para cada uno f in F(z,p). Combine eso con la división de prueba para la prueba de primalidad, y obtendrá un O(scary)algoritmo.

Sp3000
fuente
+1 paraO(scary)
AdmBorkBork
1
Buen truco para configurar i en None.
lirtosiast
3

Perl, 124 bytes

$p=prime_iterator;y/1379//or$i=+~print'Empty Set'}while($i<100){$_=&$p;is_prime"$`@F$'"or redo while//g;$i++

Requiere la siguiente opción de línea de comando:, -palMntheory=:allcontada como 16. Entrada tomada de stdin.

Utiliza el módulo de @DanaJMath::Prime::Util para perl (cargado con el pragma ntheory). Consíguelo con:

cpan install Math::Prime::Util
cpan install Math::Prime::Util::GMP

is_primees determinista para todos los valores inferiores a 2 64 , lo cual es suficiente para nuestros propósitos.


Uso de muestra

$ echo 2|perl -palMntheory=:all oscary.pl
Empty Set

$ echo 7|perl -palMntheory=:all oscary.pl
3
19
97
433
487
541
691
757
853
1471
.
.
.
718705783
720574573
737773357
745157779
747215167
767717017
768743377
770294977
771778477
774577777

Tiempos de ejecución esperados

x = 1 : 1m 09.2s
x = 3 : 0m 04.2s
x = 7 : 2m 52.5s
x = 9 : 0m 11.5s

primo
fuente
1

Pyth, 58

L}bPb|*"Empty Set"}Qj204568T.f&yZ.Amyi++<JjZTdQ>JdThl`Z100

Este conjunto de pruebas solo calcula los primeros 10 números porque lleva demasiado tiempo generar el resto. La fuerza bruta fuerza tanto la originalidad como la inserción de los dígitos. Demuestra un rendimiento tan malo que no he podido ejecutarlo hasta 100, así que dígame si hay problemas.

FryAmTheEggman
fuente