El matemático griego Euclides muy bien pudo haber demostrado, alrededor del 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 ”.¿Esto es excelente?“
Lanzado hace cinco años, el juego superó los tres millones de intentos el 16 de julio, o, más concretamente, alcanzó la carrera 2,999,999, después de una Publicación de Hacker News 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 está encendido La aperiódical, un blog de matemáticas d el 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, quien trabaja en la unidad de aprendizaje electrónico en la Escuela 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 recibir una respuesta del estudiante, que automáticamente marca y da retroalimentación”, dice. “Podrías ver el juego de los números primos como una especie de evaluación”, lo ha utilizado cuando realiza sesiones de divulgación en las escuelas.
Hizo el juego un poco más fácil con atajos de teclado (las teclas yyn hacen clic en los botones sí-no correspondientes en la pantalla) para ahorrar tiempo de movimiento del mouse.
Darle un giro:
Algoritmos de verificación de primalidad
Los números primos tienen una utilidad práctica en la informática, como los códigos de corrección de errores y el cifrado. Pero mientras que la factorización primaria 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 Alexander Grothendieck
El algoritmo más minimalista para verificar la primacía de un número es la división de prueba: divida el número por cada número 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 el calculador más infatigable”.
El algoritmo Lawson-Perfect codificado para el juego se llama prueba de primordialidad Miller-Rabin (que se basa en un método del siglo XVII muy eficiente, pero no blindado, “El pequeño teorema de Fermat”). La prueba de Miller-Rabin funciona sorprendentemente bien. En lo que respecta a Lawson-Perfect, es “básicamente mágico”: “No entiendo realmente cómo funciona, pero estoy seguro de que podría hacerlo si dedicara el tiempo a analizarlo más profundamente”, dice.
Dado que la prueba utiliza aleatoriedad, produce un resultado probabilístico. Lo que significa que a veces la prueba miente. “Existe la posibilidad de descubrir a un impostor, un número compuesto que intenta pasar como primo”, dice Carl Pomerance, matemático de 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 inteligente 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 la primalidad, la prueba de Miller-Rabin es “la punta del iceberg”, dice Pomerance. En particular, hace 19 años, tres científicos informáticos, Manindra Agrawal, Neeraj Kayal y Nitin Saxena, todos en el Instituto Indio de Tecnología Kanpur, anunciaron la Prueba de primalidad de AKS (nuevamente basado en el método de Fermat), que finalmente proporcionó una prueba para demostrar de manera inequívoca 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. De vez en cuando, Lawson-Perfect recibe correos electrónicos de personas interesadas en compartir sus puntuaciones más altas en el juego. Recientemente, un jugador informó 60 primos en 60 segundos, pero el récord es más probable de 127 (Lawson-Perfect no registra las puntuaciones altas; sabe que hay algunos tramposos, con intentos asistidos por computadora que producen picos en los datos).
El puntaje de 127 fue logrado por 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 el mínimo de 3.000”, dice. “Supongo que algunos dirían que incluso eso es excesivo”.
La investigación de Fernando está 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, calcula que 127 sería muy difícil de superar. Y, dice, “simplemente se siente bien detenerse en un récord de números primos”.
