El número 113
es el primer primo cuya longitud 3
es primo, la suma digital 5 = 1 + 1 + 3
es primo y el producto digital3 = 1 * 1 * 3
es primo.
Un primo que tiene estas 3 propiedades se llamará supremamente primo . Los primos 11117
y 1111151
son otros ejemplos.
Gol
Escriba un programa que pueda encontrar el número primo supremo más grande posible en menos de una hora en una computadora personal moderna decente (como la especificación preferida aquí ).
No deberías simplemente darnos una gran prima suprema. Debe mostrarnos su proceso de búsqueda con el código que realmente funciona. Puede aprovechar sus soluciones o las de otras personas, pero asegúrese de darles crédito. Estamos intentando comunalmente encontrar el mayor prime supremo realizable en una computadora normal en una hora.
Tanteo
La sumisión que encuentra el mayor premio supremo gana. Si resulta que hay muchos primos supremos finitos, entonces la primera sumisión que genera el primo supremo más alto gana.
(Si puedes demostrar matemáticamente que hay o no hay infinitos números primos supremos, te daré 200 repeticiones por recompensa solo porque :))
Detalles
- Puede usar cualquier fuente para generar sus primos (por ejemplo, internet).
- Puede usar métodos de prueba primarios probabilísticos.
- Todo está en la base 10.
- Cero y uno NO se consideran primos.
- Los premios que contienen
0
tienen un producto digital de0
modo que obviamente no pueden ser supremos. Para mantener la página menos abarrotada, ponga primos supremos grandes (más de 100 dígitos) en la forma:
{[number of 1's before the prime digit]}[prime digit]{[number of 1's after the prime digit]}
Entonces
1111151
podría expresarse como{5}5{1}
.
fuente
Respuestas:
Perl, 15101 dígitos, {83} 7 {15017}, 8 minutos. Max encontrado: 72227 dígitos
Usando mi módulo Math :: Prime :: Util y su back end GMP . Tiene una serie de pruebas de composición que incluyen is_prob_prime () con una prueba ES BPSW (un poco más estricta que la ispseudoprime de Pari), is_prime () que agrega un MR de base aleatoria y is_provable_prime () que ejecutará BLS75 T5 o ECPP. En estos tamaños y tipos, hacer una prueba llevará mucho tiempo. Lancé otra prueba de MR en el sub verificador pedante. Veces en un Core2 E7500 que definitivamente no es mi computadora más rápida (toma 2.5 minutos en mi i7-4770K).
Como señala Tim S., podríamos seguir buscando valores más grandes, hasta el punto en que una sola prueba tome una hora. Con ~ 15000 dígitos en este E7500, toma alrededor de 26 segundos para una prueba de MR y 2 minutos para el is_prime completo (división de prueba más MR de base-2 más ES Lucas más un MR de base aleatoria). Mi i7-4770K es más de 3 veces más rápido. Probé algunos tamaños, principalmente viendo cómo le fue en los resultados de otras personas. Intenté 8k, 20k y 16k, matando cada uno después de ~ 5 minutos. Luego probé 15k en progresión durante ~ 10m cada uno y tuve suerte en el 4to.
Las pruebas de PRP de OpenPFGW son ciertamente más rápidas una vez que pasan más de 4000 dígitos, y mucho más rápido en el rango de 50k +. Sin embargo, su prueba tiene una buena cantidad de falsos positivos, lo que lo convierte en una excelente prueba previa, pero a uno todavía le gustaría verificar los resultados con otra cosa.
Esto podría ser paralelizado con hilos perl o usando MCE similar a los ejemplos paralelos de buscador de Fibonacci en el módulo.
Tiempo y resultados en un i7-4770K inactivo con un solo núcleo:
Para el resultado de 32k dígitos, comencé a ejecutar 6 scripts al mismo tiempo, cada uno con argumentos sucesivos a partir de 32000. Después de 26.5 minutos, uno terminó con el resultado de 32063 dígitos mostrado. Por 57k, dejé que las secuencias de comandos sucesivas se ejecutaran 6 a la vez durante una hora en incrementos de entrada de 500 hasta que el resultado de 57k regresó en 57 minutos. El resultado de 72k dígitos se encontró haciendo primos sucesivos desde 70k en adelante, por lo que definitivamente no se encuentra en una hora (aunque una vez que sabe por dónde empezar, lo es).
La secuencia de comandos:
fuente
gmpy2
y PyPy conmy_math
): codepad.org/aSzc0esTforprimes { ...do stuff... } 1e7;
que incluyen 10 veces o más rápido (felicitaciones a Pari / GP por muchas buenas ideas). Siempre agradezco los comentarios, así que avíseme si algo no funciona de la manera deseada.Python 2.7 en PyPy, {2404} 3 {1596} (~ 10 ^ 4000)
Encontré este aproximadamente 50 minutos después de comenzar desde 4000. Por lo tanto, estimaría que este es el límite superior de este enfoque de código.
Cambio: He notado que algunas longitudes parecen ser más fructíferas para generar este tipo de primo que otras, por lo que he decidido verificar solo 50 ubicaciones aleatorias del dígito que no es 1 en lugar de todas las ubicaciones posibles, antes de mover en. No estoy completamente seguro de que esto mejore el rendimiento, o que 50 sea correcto, pero ya veremos.
La lista de posibilidades se genera en función del hecho de que para que se cumplan los requisitos de los productos, el número debe ser todos excepto un primo. Además, el primo no puede ser 2 debido a la relación de suma y longitud, y la suma digital no debe ser divisible por tres, dando los requisitos de% 3.
is_prime tomado de http://codepad.org/KtXsydxK , escrito por @primo
Nota: esta función is_prime es en realidad una prueba de pseudoprime Baillie-PSW, pero no hay contraejemplos conocidos, por lo que no me preocuparé por la distinción.
fuente
is_very_very_very_very_very_very_very_probably_prime()
...PARI / GP, 4127 dígitos
(10 4127 -1) / 9 + 2 * 10 515
Esta es una búsqueda bastante sencilla: verifique solo las longitudes de los dígitos primos, luego calcule los posibles números primos para usar, luego repita todas las posibilidades. Encerré en especial los casos comunes donde hay 0 o 1 dígitos primos adecuados para usar.
Esto tomó 36 minutos para calcular en un núcleo de una máquina bastante vieja. Estoy seguro de que no tendría problemas para encontrar un número primo de más de 5000 dígitos en una hora, pero también soy impaciente.
Una mejor solución sería usar cualquier lenguaje razonable para hacer todo menos el bucle más interno, luego construir un archivo abc para primeform que esté optimizado para ese tipo particular de cálculo. Esto debería ser capaz de llevar el cálculo hasta al menos 10,000 dígitos.
Editar : Implementé la solución híbrida descrita anteriormente, pero en mi máquina anterior no puedo encontrar el primer término con> = 10,000 dígitos en menos de una hora. A menos que lo ejecute en algo más rápido, tendré que cambiar a un objetivo menos elevado.
fuente
Mathematica 3181 dígitos
Actualización: Hubo algunos errores graves en mi primera presentación. Pude dedicar algo de tiempo a verificar los resultados de este. La salida está formateada como una lista de dígitos. Eso facilita la comprobación de cada una de las condiciones.
Ejemplo
Esta fue mi primera prueba, una búsqueda de una solución con 3181 dígitos. Encontró el primer caso en 26 segundos.
Veamos el razonamiento. Luego entraremos en el programa en sí.
Comencemos, como lo hice, "¿Cuál es el número 450?" ¿Podemos encontrar una solución con tantos dígitos (3181)?
El número se encuentra uniendo los dígitos.
Pero en lugar de mostrarlo, podemos preguntar cuáles son los dígitos y dónde se encuentran.
Esto significa que hubo 3180 instancias del dígito 1 y una sola instancia del dígito 7.
¿En qué posición está el dígito 7?
Entonces el dígito 7 es el dígito 142. Todos los demás son de 1.
Por supuesto, el producto de los dígitos debe ser primo, es decir, 7.
Y la suma de los dígitos también es primo.
Y sabemos que el número de dígitos es primo. Recuerde, seleccionamos el número 450, es decir, 3118.
Entonces se han cumplido todas las condiciones.
fuente
4002 * 1 + 7 = 4009
y no 4003 de acuerdo con las especificaciones.Python 2.7, 6217 dígitos: {23} 5 {6193} 6 minutos 51 segundos
Estaba trabajando en mi propia versión y me decepcionó ver que @issacg me había golpeado con un enfoque muy similar, aunque con is_ (muy_probablemente) _prime (). Sin embargo, veo que tengo algunas diferencias significativas que resultan en una mejor respuesta en menos tiempo (cuando también uso is_prime). Para aclarar esto, cuando también empiezo desde 4000, llego a una mejor respuesta de 4001 dígitos ({393} 7 {3607}) en solo 26 minutos, 37 segundos usando el intérprete estándar de Python (también en la versión 2.7), no el PyPy versión. Además, no estoy revisando los números. Todos los candidatos son verificados.
Aquí están las mejoras principales:
Use un generador principal ( https://stackoverflow.com/questions/567222/simple-prime-generator-in-python/568618#568618 ) para crear una lista de primos para verificar y (su versión de "primos pequeños") y para generar longitudes de número elegibles.
Queremos pasar nuestro tiempo buscando el primo supremo más grande de una longitud determinada, no el más pequeño, por lo tanto, primero construyo los números más grandes posibles para verificar, no el más pequeño. Luego, una vez que se encuentra uno, podemos pasar inmediatamente a la siguiente longitud.
EDITAR: ahora con multiprocesamiento
Este es un cambio significativo a las versiones anteriores. Antes, noté que mi máquina de 8 núcleos apenas funcionaba, así que decidí probar suerte en el multiprocesamiento en Python (primera vez). ¡Los resultados son muy buenos!
En esta versión, se generan 7 procesos hijos, que toman una 'tarea' de una lista de posibles posibilidades (num_length + dígitos elegibles). Agitan intentando diferentes posiciones [7,5,3] hasta encontrar una. Si lo hace, informa al proceso maestro de la nueva longitud más larga que se ha encontrado. Si los niños están trabajando en una longitud num_ que es más corta, simplemente salen bajo fianza y obtienen la siguiente longitud.
Comencé esta ejecución con 6000, y todavía se está ejecutando, pero hasta ahora, estoy muy satisfecho con los resultados.
El programa aún no se detiene correctamente, pero no es un gran problema para mí.
Ahora el código:
fuente
my_math
también se puede usar para generar una lista de primos, a lawhile prime < 20006: prime = next_prime(prime)
. Parece ser aproximadamente 3 veces más rápidogen_primes
y mucho más eficiente en memoria.DO, GMP - {7224} 5 {564} = 7789
Felicitaciones a @issacg y a todos ustedes por las inspiraciones y trucos.
Y también el autor de la pregunta magistral @ Calvin's Hobbies para esta pregunta.
Compilar:
gcc -I/usr/local/include -o p_out p.c -pthread -L/usr/local/lib -lgmp
Si tiene ganas de donar su capacidad de cálculo o tiene curiosidad por el rendimiento, no dude en copiar el código y compilarlo. ;) Necesitará GMP instalado.
fuente
PFGW, 6067 dígitos, {5956} 7 {110}
Ejecute PFGW con el siguiente archivo de entrada y
-f100
prefactorice los números. En aproximadamente 2-3 minutos de CPU en mi computadora (i5 Haswell), encuentra el PRP (10 ^ (6073-6) -1) / 9 + 6 * 10 ^ 110, o {5956} 7 {110} . Elegí 6000 dígitos como punto de partida como un número nada bajo la manga que es un poco más alto que todas las presentaciones anteriores.Según lo rápido que pude encontrar este, pude aumentar fácilmente la cantidad de dígitos y aún así encontrar un PRP en una hora. Con la forma en que se escriben las reglas, incluso podría encontrar el tamaño en el que mi CPU, que se ejecuta en los 4 núcleos, puede terminar una prueba de PRP en una hora, tomar mucho tiempo para encontrar un PRP y hacer que mi "búsqueda" consista únicamente del único PRP.
PD: En algunos sentidos, esta no es una solución de "código" porque no escribí nada más que el archivo de entrada ... pero entonces, muchas soluciones de Mathematica de una línea para problemas matemáticos podrían describirse de la misma manera, como podría usando una biblioteca que hace el trabajo duro por ti. En realidad, creo que es difícil trazar una buena línea entre los dos. Si lo desea, podría escribir un script que cree el archivo de entrada PFGW y llame a PFGW. El script incluso podría buscar en paralelo, para usar los 4 núcleos y acelerar la búsqueda ~ 4 veces (en mi CPU).
PPS Creo que LLR puede hacer las pruebas de PRP para estos números, y espero que sea mucho más rápido que PFGW . Un programa de tamizado dedicado también podría ser mejor para factorizar estos números que el PFGW de uno en uno. Si combina estos, estoy seguro de que podría superar los límites mucho más que las soluciones actuales.
fuente
Python 2.7, 17-19 dígitos
Encontrado 5111111111111 (13 dígitos) en 3 segundos y este primo supremo de 17 dígitos en 3 minutos. Supongo que la máquina de destino podría ejecutar esto y obtener un primo supremo de 19 dígitos en menos de una hora. Este enfoque no escala bien porque mantiene primos de hasta la mitad del número de dígitos objetivo en la memoria. La búsqueda de 17 dígitos requiere el almacenamiento de una matriz de 100M booleanos. 19 dígitos requerirían una matriz de elementos 1B, y la memoria se agotaría antes de llegar a 23 dígitos. El tiempo de ejecución probablemente también lo sería.
Los enfoques de prueba de primalidad que no involucren una variedad ridículamente grande de primos divisores funcionarán mucho mejor.
fuente
Mathematica
42114259 dígitosCon el número:
{1042} 7 {3168}{388} 3 {3870}El cual fue generado por el siguiente código:
Los lanzamientos hacen que deje de probar otros números con los mismos dígitos que el que se encuentra actualmente. Dado que comienza a probar en el dígito más significativo, esto significa que siempre devuelve el número más grande a menos que el número de dígitos sea miembro de un triplete primo.
Simplemente comenzó a probar justo debajo del valor de una de las respuestas anteriores :)
Una vez que finaliza, el número se almacena en la variable curlargest
fuente
JavaScript, 3019 dígitos, {2,273} 5 {745}
Esto utiliza la prueba MillerRabin incluida en BigInteger.js por Tom Wu.
A partir de 0 => 2,046 dígitos = {1799} 7 {263} en una hora .
A partir de 3000 => 3,019 dígitos = {2,273} 5 {745} en una hora, menos 3 segundos .
Cuando comenzó desde 0, el programa saltó hacia adelante y comenzó a buscar nuevamente a una longitud de 1.5X la longitud del último s-prime encontrado. Luego, cuando vi lo rápido que estaba funcionando, supuse que encontraría uno a partir de 3000 en una hora, lo que hizo con solo 3 segundos de sobra.
Puede probarlo aquí: http://goo.gl/t3TmTk
(configurado para calcular todos los primos-s, o salte adelante).
El programa funciona construyendo cadenas de todos los "1", pero con un "3", "5" o "7". Agregué una verificación rápida en la función IsStrPrime para rechazar los números que terminan en "5".
Esto fue muy divertido. Me recuerda a un rompecabezas que hice hace muchos años para calcular lo que se llama un dígito eliminado primo . Este es un número primo que si elimina cualquier dígito, el número restante sigue siendo primo. Por ejemplo, 1037 es un dígito eliminado primo porque 1037, 037, 137, 107 y 103 son primos. Encontré uno de 84 dígitos de largo, y el más largo que conozco es de 332 dígitos. Estoy seguro de que podríamos encontrar uno mucho más largo con las técnicas utilizadas para este rompecabezas. (Pero elegir los números de prueba es un poco más complicado, ¿tal vez?)
fuente
Axioma, 3019 dígitos {318} 5 {2700}
resultado del valor inicial 3000 en 529 segundos
fuente