¿Cuál es el entero positivo más pequeño que tiene primalidad desconocida?

Answer 1

Joseph Lurie da una buena respuesta sobre la inutilidad de tratar de precisar un número real.

Preguntas similares se han empantanado tratando de definir qué significa “conocido”. Todos los números primos en secuencia se han generado a 4e18, pero algunos han argumentado ya que no los almacenaron todos (los recuentos a intervalos pequeños se almacenan), eso no se aplica. Todas las PSP de base 2 a 2 ^ 64 se han enumerado utilizando cálculos matemáticos inteligentes y muchos cálculos, lo que nos permite tener pruebas deterministas de un solo microsegundo para cualquier entrada de 64 bits, pero de nuevo, ¿eso cuenta?

Para dar una idea de la practicidad de las pruebas, a 250 dígitos , podemos identificar casi todos los compuestos en menos de 1 milisegundo (el costo de una prueba BPSW), y completar una prueba de primalidad en menos de 1 segundo. Para pequeños números de 30 dígitos, estos son mucho más rápidos. El problema para la pregunta es que hay tantos números que no tiene mucho sentido intentar enumerarlos, dada la velocidad de las pruebas individuales, la total impracticabilidad de tratar de almacenarlos y la utilidad casi nula de dicha lista. Tenga en cuenta que almacenar solo los pequeños primos de 64 bits de una manera simple (adecuado para la búsqueda) tomaría más de 3 exabytes, 28 veces más grande que la matriz de almacenamiento más grande actual. Una vez que haya pasado los tamaños triviales, es mejor que genere números primos o pruebe primalidad en lugar de intentar buscarlos en tablas gigantes.

Answer 2

Esto es, en efecto, la paradoja de Berry. Probar la primalidad de cualquier número entero es una tarea rutinaria para una computadora. El único caso en el que la primalidad de un entero particular sería desconocido es si nadie se ha molestado en ejecutar una prueba de primalidad en él. Este es un estado de cosas razonable para los números grandes arbitrarios, pero si de alguna manera identificamos el número entero más pequeño que aún no se había probado, la primalidad de ese entero sería una pregunta lo suficientemente interesante como para realizar una prueba de primalidad en él inmediatamente, anulando así su estado como el menor entero de primalidad desconocida.