¿57 es un número primo? Hay un juego para eso.

Sra. Tecnología | pixabay

El matemático griego Euclides muy bien pudo haber demostrado, alrededor del año 300 a. C., que hay infinitos números primos. Pero fue el matemático británico Christian Lawson-Perfect quien, más recientemente, ideó el juego de computadora ¿Es esto principal?

Lanzado hace cinco años, el juego superó los tres millones de intentos el 16 de julio, o, más concretamente, llegó a ejecutar 2.999.999, después de un Publicación de noticias de piratas informáticos generó una oleada de alrededor de 100.000 intentos.

El objetivo del juego es clasificar tantos números como sea posible en primos o no primos en 60 segundos (como Lawson-Perfect originalmente descrito en La aperiódica l, un blog de matemáticas del que es fundador y editor).

Un número primo es un número entero con exactamente dos divisores, 1 y él mismo.

Es muy simple, pero exasperantemente difícil, dice Lawson-Perfect, que trabaja en la unidad de aprendizaje electrónico en la Facultad de Matemáticas y Estadística de la Universidad de Newcastle. Creó el juego en su tiempo libre, pero resultó útil en el trabajo: Lawson-Perfect escribe software de evaluación electrónica (sistemas que evalúan el aprendizaje). El sistema que hago está diseñado para generar aleatoriamente una pregunta de matemáticas y tomar una respuesta del estudiante, que automáticamente marca y da retroalimentación, dice. Podría ver el juego de números primos como una especie de evaluación: lo ha usado cuando realizaba sesiones de divulgación en las escuelas.

Hizo que el juego fuera un poco más fácil con atajos de teclado (las teclas y y n hacen clic en los botones correspondientes de sí o no en la pantalla) para ahorrar tiempo al mover el mouse.

Darle un giro:

Algoritmos de verificación de primalidad

Los números primos tienen una utilidad práctica en la informática, como con los códigos de corrección de errores y el cifrado. Pero mientras que la factorización prima es difícil (de ahí su valor en el cifrado), la verificación de la primalidad es más fácil, aunque complicada. El matemático alemán ganador de la Medalla Fields Alejandro Grothendieck infamemente confundido 57 para primo (el primo de Grothendieck). Cuando Lawson-Perfecto datos analizados del juego , encontró que varios números exhibían una cierta Grothendieckyness. El número que más a menudo se confundió con un primo fue 51, seguido de 57, 87, 91, 119 y 133, el némesis de Lawson-Perfect (también ideó un práctico servicio de verificación de primalidad: https://isthisprime.com/2 ).

El algoritmo más minimalista para verificar la primacía de un número es la división de prueba: divide el número entre todos los números hasta su raíz cuadrada (el producto de dos números mayores que la raíz cuadrada sería mayor que el número en cuestión).

Sin embargo, este método ingenuo no es muy eficiente, y tampoco lo son algunas otras técnicas ideadas a lo largo de los siglos; como observó el matemático alemán Carl Friedrich Gauss en 1801, requieren un trabajo intolerable incluso para la calculadora más infatigable.

El algoritmo Lawson-Perfect codificado para el juego se denomina prueba de primalidad de Miller-Rabin (que se basa en un método muy eficiente pero no férreo del siglo XVII, El pequeño teorema de Fermat ). La prueba de Miller-Rabin funciona sorprendentemente bien. En lo que se refiere a Lawson-Perfect, es básicamente magia: no entiendo realmente cómo funciona, pero estoy seguro de que podría hacerlo si me tomara el tiempo de analizarlo más a fondo, dice.

Dado que la prueba utiliza la aleatoriedad, produce un resultado probabilístico. Lo que significa que a veces la prueba miente. Existe la posibilidad de descubrir un impostor, un número compuesto que intenta hacerse pasar por primo, dice Carl Pomerance, matemático del Dartmouth College y coautor del libro. Números primos: una perspectiva computacional . Sin embargo, las posibilidades de que un impostor se deslice a través del ingenioso mecanismo de verificación del algoritmo son quizás una en un billón, por lo que la prueba es bastante segura.

Pero en lo que respecta a los algoritmos inteligentes de verificación de primalidad, la prueba de Miller-Rabin es la punta del iceberg, dice Pomerance. En particular, hace 19 años, tres informáticos —Manindra Agrawal, Neeraj Kayal y Nitin Saxena, todos del Instituto Indio de Tecnología de Kanpur— anunciaron la Prueba de primalidad AKS (nuevamente basado en el método de Fermat), que finalmente proporcionó una prueba para demostrar inequívocamente que un número es primo, sin aleatorización y (teóricamente, al menos) con una velocidad impresionante. Por desgracia, rápido en teoría no siempre se traduce en rápido en la vida real, por lo que la prueba AKS no es útil para fines prácticos.

El récord mundial no oficial

Pero la practicidad no siempre es el punto. Ocasionalmente, Lawson-Perfect recibe correos electrónicos de personas deseosas de compartir sus puntajes más altos en el juego. Recientemente, un jugador reportó 60 números primos en 60 segundos, pero es más probable que el récord sea de 127. (Lawson-Perfect no rastrea puntajes altos; él sabe que hay algunos tramposos, con intentos asistidos por computadora que producen picos en los datos).

El puntaje de 127 lo logró Ravi Fernando, un estudiante graduado de matemáticas en la Universidad de California, Berkeley, quien publicó el resultado en julio de 2020 . Sigue siendo su mejor marca personal y, según él, el récord mundial no oficial.

Desde el verano pasado, Fernando no ha jugado mucho con la configuración predeterminada, pero lo ha intentado con configuraciones personalizadas, seleccionando números más grandes y permitiendo límites de tiempo más largos: anotó 240 con un límite de cinco minutos. Lo que requirió muchas conjeturas, porque los números entraron en el rango alto de cuatro dígitos y solo he memorizado números primos hasta los 3000, dice. Supongo que algunos dirían que incluso eso es excesivo.

La investigación de Fernando es en geometría algebraica, que involucra números primos hasta cierto punto. Pero, dice, mi investigación tiene más que ver con por qué dejé de jugar que por qué empecé (comenzó su doctorado en 2014). Además, cree que 127 sería muy difícil de superar. Y, dice, se siente bien detenerse en un récord de números primos.

esconder