¿Más pequeño-primer-par gemelo superior $2\uparrow\uparrow 5\ $?

Question

He buscado los primos más pequeños de más de $$N:=2\uparrow\uparrow 5=2^{65536}$$ $N$ has $19\ 729$ dígitos. Esto es bastante grande y la búsqueda de números primos de esta magnitud no es fácil.

Encontré $$N+44\ 061$$

Esto encaja bien con el hecho de que un número de cerca de $N$ es primo con una probabilidad de $1:45\ 426$

Pero el siguiente primo es sorprendentemente

$$N+44\ 181$$

¿Se me olvida alguno de los números primos ? En otras palabras, son los otros números de $N$ $N+44\ 181$compuesto ?

Incluso el uso de la muy rápido pfgw-el primer software de pruebas, me tomó alrededor de la mitad de un día para obtener los números primos. Así que, me pregunto si podemos calcular la más pequeña de doble prime-par por encima del $N$ (Si no lo ha hecho ya).

¿Alguien tiene una idea de cómo podemos encontrar el más pequeño de twin primer par por encima del $N$ con una cantidad razonable de tiempo ?

La única idea que tengo es la de tamiz fuera el candidato de pares por la prueba de la división, pero no podría ser un mejor método.

Answer 1

No se pierda ninguna. Con $n = 2^{65536}$, $n+44061$ es un PRP como es $n+44181$. Todos los otros números de $n$ $n+44181$son compuestos.

No hay ninguna doble de los números primos en el rango de $n$$n+10\ 000\ 000$.

Al mejor de mi conocimiento, de la mejor manera para hacer esto no es dis-similar a lo que usted ha dicho:

• escoge un rango y colarla. Una vez en razonable profundidades, el rango de longitud de no tener un gran impacto en el rendimiento, pero la profundidad. Para mi prueba con el su $n$ y una longitud de 10M, mi programa eligió a una profundidad predeterminada de 5243M, dejando aproximadamente 8300 candidatos después de ~3 minutos. Debería haber elegido tamiz más profundo. ~600 de los candidatos que abandonan después de que a sólo 6 minutos más de tamizado.

• Desde el tamizado de la gama, los candidatos son los $n$ donde $n$ $n+2$ ambos han sobrevivido tamizado.

• Ejecutar un rápido compositeness prueba sobre ellos. En este tamaño PFGW la prueba de Fermat es el más eficiente. Que normalmente significa la ejecución de múltiples programas que se ejecutan a través de los archivos intermedios. Yo uso GMP todo, lo que es más conveniente, pero no un rendimiento ideal para estas sobre-10k-números de dos dígitos. Yo uso una de Miller-Rabin base 2 de la prueba, que es aproximadamente la misma velocidad como una prueba de Fermat en GMP.

• Verificar si los resultados de ambos pasan la primera prueba. Yo uso el ES Lucas de la prueba, lo que significa que los resultados son extra fuertes BPSW probable de los números primos ya que he usado una base-2 MR prueba a empezar. Si el uso de PFGW, sólo tiene que ejecutar a través de un BPSW de prueba de uno de los muchos paquetes que tienen una BPSW prueba (PFGW incluye una versión, pero tendrías que buscar cómo se aplican). Esto es suficiente para la mayoría de propósitos, pero se puede ejecutar un par de pruebas más, si se desea.