¿Cómo fue el 506-dígitos de número primo 999...9998999...999 encontrado?

Question

Me sorprendió encontrar a una reclamación hecha en el internet que el siguiente número es primo:

99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999989999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999

Todo 9s a excepción de uno 8. Este 506-número de dígitos no se ven especialmente privilegiada para mí. No lo pude encontrar en cualquier disposición del público las listas (que clonk alrededor de 8 dígitos), así que hice la prueba de la división hasta 626543489 y, a continuación, hizo Miller-Rabin con 5000 rondas (overkill). Parece que, en realidad, para ser primer.

---

Mi pregunta es:¿hay algo importante acerca de este número que nos ayudaría a darnos cuenta de que es primo? ¿Cómo se encuentra?

No es un Mersenne, Fermat, o Perfecto prime, por ejemplo. No es particularmente grande (el más grande que se conoce de este escrito es en las decenas de millones de dígitos), pero sospecho que el anterior y siguiente números primos no son conocidos.

Answer 1

Se puede demostrar primer uso de Curva Elíptica Primalidad Demostrando; he comprobado el uso de Primo que sólo dura un par de segundos.

Cómo se encuentra? El proceso probablemente fue:

• Hacer una lista de aspecto interesante de los números.
• Filtro de la lista mediante la prueba de la división.
• En el resto de los números, el uso de un rápido pseudo-primalidad de prueba (por ejemplo, de Fermat de la prueba).
• Compruebe los que pasan la pseudo-primalidad de prueba utilizando Primo.

Answer 2

Al principio pensé que era un capicúa prime. Hay un montón de variaciones, y el más grande actualmente conocida 474,501 dígitos (Wikipedia parece estar fuera de fecha -- de ver El Primer Páginas). Para los 3 primeros, tienen algo de la forma M+1, donde M es principalmente factorable, por lo tanto, un BLS75 n-1 prueba de que se puede hacer.

Podemos encontrar palindrómicas de los números primos de este tipo con un montón de herramientas, por ejemplo:

perl -Mntheory=:all -E '$s=8; for (1..3000) { $s="9${s}9"; say if is_prime($s); }'

encuentra bastante un par de ejemplos, incluyendo el 757 de dígitos primer formada por un ocho con 378 nueves en cada lado. Hay un montón de métodos de prueba de que funciona para los números de este tamaño: WraithX APR-CL, Alpertron APR-CL, Pari/GP APR-CL, mi ECPP-DJ o Perl/ntheory, y Primo de la ECPP, entre otros.

La mayoría de los métodos de prueba de trabajo bastante bien hasta 2-3k dígitos. Primo es el único instrumento que sobresale más allá de eso, y ha sido utilizado hasta 30k dígitos (un largo compromiso en un fuerte de la máquina).

Pero el ejemplo que dio no es un palíndromo, ya que tiene 252 nueves en un lado y 253 en el otro. Podemos encontrar mediante la sustitución de la $s=8 con $s=89 en la secuencia de comandos anterior, junto con los dos más pequeños y más grandes de los números primos con la misma forma. Si el uso de algo como Pari/GP podría ser mejor usar una forma diferente de escribir el número, por ejemplo,$10^{506}-10^{253}-1$, en lugar de utilizar cadenas.

Por último, podemos mirar http://factordb.com y ver que este número ha estado en la base de datos de al menos 5 años, con un N+1 prueba. Creo factordb así como los números primos páginas utiliza PFGW para la prueba, que por desgracia no la salida de un certificado, incluso a pesar de que uno debe ser fácilmente construido durante la prueba (es cierto que no es difícil de ejecutar de nuevo debido a la factorización, pero sería agradable ser capaz de comprobar el certificado como podemos hacer con el Primo).