El más pequeño $1\ 000$ número de dígitos $x$ , de tal manera que $x$ , $x+2$ y $x+6$ ¿son todos primos?

Question

Actualmente estoy buscando el más pequeño $1\ 000$ número de dígitos $x$ , como el sombrero $x,x+2,x+6$ son todos primos (un triple así también se llama constelación prima). Para ello, escribí este programa PARI/GP :

? x=prod(j=1,10,prime(j));z=prod(j=1,3*10^4,prime(j));a=10^999-1;gef=0;while(gef
==0,a=a+2;if(gcd(a*(a+2)*(a+6),x)==1,if(gcd(a*(a+2)*(a+6),z)==1,if(ispseudoprime
(a,1)==1,print(a-10^999);if(ispseudoprime(a+2,1)==1,print(a);if(ispseudoprime(a+
6,1)==1,gef=1))))))

Como mi ordenador no es el más rápido, sólo llegué a unos $x=10^{999}+491\cdot 10^6$ y no encontró ningún triple.

Mi estrategia fue

• Comprobando que $x(x+2)(x+6)$ no tiene ningún factor primo hasta $29$
• Comprobando que $x(x+2)(x+6)$ no tiene ningún factor primo hasta el $30\ 000$ el primero
• Comprobación de las cifras $x$ , $x+2$ , $x+6$ uno tras otro.

¿Puedo acelerar más el programa? Tal vez, hay un método de tamizado adecuado para esta tarea.

Por supuesto, invito a todo el mundo a realizar la tarea en otro software, quizás más potente. Continuaré mi búsqueda, pero podría ser todavía un largo camino para encontrar el triple más pequeño.

Answer 1

Existen métodos rápidos de cribado para encontrar agrupaciones primarias. Generalmente estos trabajan con trozos de algún tamaño primitivo, habiendo construido residuos aceptables para el cluster. Por ejemplo, mod 30 sólo hay 2 valores posibles para iniciar un triple (0,2,6), sólo 8 mod 210, 64 mod 2310, etc. Cuanto más grande sea el clúster, menos residuos aceptables y por lo tanto más rápido funciona. Desgraciadamente, con un triple no obtenemos ni de lejos el beneficio de este método como lo hacemos con clusters más grandes.

Charles tiene algunas ideas y código Pari/GP para trillizos en este post de Mersenneforum .

Tengo un código en Perl/ntheory que hace un trabajo decente para encontrar clusters. Estoy seguro de que hay software más rápido, pero no he encontrado nada de código abierto. Por otra parte, algunos investigadores que trabajan actualmente en esta área son Sorenson , Waldvogel y Wroblewski. He discutido ideas con Waldvogel y parece que hacemos básicamente lo mismo, aunque es difícil comparar ya que su trabajo, como el de los demás, es de código cerrado.

En tu ejemplo, la búsqueda hasta 10^7 ha llevado 45 segundos sin encontrar soluciones. Eso es sólo 2 veces más rápido que tu código. Pero también hay un ejemplo script que ejecuta estos en paralelo, por lo que en una máquina rápida podemos obtener algún speedup lineal.

Después de unas 2 horas encontró 10^999 + 5537073001.

Answer 2

La más trivial de las mejoras es utilizar el hecho de que $x$ (o $a$ en su programa) debe ser $5$ modulo $6$ (debe ser impar, y ninguno de $x$ , $x+2$ , $x+6$ puede ser un múltiplo de $3$ ). Así que puedes empezar $a$ en $10^{999}-5$ y aumentarlo en pasos de 6.

El cribado también es posible, y puede sustituir los cálculos de gcd de su programa. Sospecho que acelerará las cosas.
Basta con establecer una matriz de banderas, que representan los números $10^{999}$ a $10^{999}+n$ . A continuación, marque todos los múltiplos de 2, todos los múltiplos de 3, todos los múltiplos de 5, ... todos los múltiplos del primo p, ... para el número de primos que desee utilizar. Los números representados por las entradas de la matriz sin marcar son los primos potenciales restantes, así que si tienes $x$ , $x+2$ , $x+6$ sin marcar puedes hacer una prueba de primalidad para ver si forman una constelación.