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, 1
y 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 x
de N , con la condición 0 <= x <= 9
, y un número y
de N , y se inserta x
en y
la expansión decimal de cada posición (es decir, anteponer, insertar o agregar x
a 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 37
y 73
son primos, 719
179
y 197
son primos, etc.
Tenga en cuenta que z (2) está vacío, porque ningún primo que tenga un 2
anexo 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 Set
deberí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
"
es innecesario, aunque es un trabajo muy agradable.Python 3, 188 bytes
Mal golf, pero aquí hay algo por ahora. En lugar de verificar
p in P and F(z,p) subset of P
, verificamos quep*f
sea un semiprime para cada unof in F(z,p)
. Combine eso con la división de prueba para la prueba de primalidad, y obtendrá unO(scary)
algoritmo.fuente
O(scary)
Perl, 124 bytes
Requiere la siguiente opción de línea de comando:,
-palMntheory=:all
contada como 16. Entrada tomada de stdin.Utiliza el módulo de @DanaJ
Math::Prime::Util
para perl (cargado con el pragmantheory
). Consíguelo con:is_prime
es determinista para todos los valores inferiores a 2 64 , lo cual es suficiente para nuestros propósitos.Uso de muestra
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
fuente
Pyth, 58
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.
fuente