Reacciones 0

primos-mersenne

En 1644 Mersenne conjeturó que los números de la forma 2n – 1 eran primos, donde n es un primo. W. W. R. Ball llamó a éstos Números de Mersenne y hasta la fecha los esfuerzos para demostrar esta conjetura han sido vanos De hecho, no se conoce cómo llegó Mersenne a este resultado, ni para cuáles condiciones se cumple Inclusive, hasta 1962 el primo más grande conocido era 244 – 1, el cual es, en sí, un número de Mersenne y consta de aproximadamente 3000 cifras.

Hay una larga historia de los primos de Mersenne, la cual comenzó en 1456 y que sigue hasta nuestros días. Se conocen 47 números primos de Mersenne (el último tiene como n = 43112609, y consta de 12,978,189 de cifras. Fue hallado en el 2008 gracias a los esfuerzos de Smith, Woltman y Kurowski usando GIMPS y PrimeNet, utilizando Prime95, una aplicación gratuita escrita por George Woltman, que es usada por GIMPS (Great Internet Mersenne Prime Search), como un proyecto distribuido dedicado exclusivamente a hallar nuevos primos de Mersenne. Prime95 se refiere al software de Windows y Mac OS X, pero hay una versión para Linux, MPrime, que funciona usando la consola, la línea de comandos. Es idéntica a Prime95, pero no tiene una interfaz gráfica como en sus contrapartes Mac y PC.

Los primeros números de Mersenne, de la forma 2n – 1 son 3, 7, 31, 127, y estos son fáciles de probar en su primalidad porque se pueden hacer las divisiones con los números anteriores al que estamos probando, pero para números muy grandes, el hacer este proceso podría llevar demasiado tiempo. Sin embargo, tenemos buenas noticias para los primos de Mersenne y es que hay una prueba rápida, llamada prueba de Lucas-Lehmer, con la que puede saberse si un número es primo o no.

El primo de Mersenne 48 fue hallado por Curtis Cooper, un matemático de la Universidad de Missouri Central. Aquí hablamos de 257,885,161 – 1 y es un número de Mersenne que tiene 17,425,170 de dígitos. El resultado se obtuvo usando los servidores distribuidos GIMPS. Este proyecto de cómputo distribuido se diseñó para “cazar” los primos de Mersenne y es responsable de descubrir los últimos 10 primos de Mersenne, habiéndose hallado en el 2008 el número 47. GIMPS corre en cerca de 1000 computadoras en diversas universidades y para hallar el primo 48 se necesitaron 39 días de cálculos. Se verificó el resultado usando un servidor de 32 núcleos en seis días.

El descubrimiento hace acreedor a Cooper a un premio de 3,000 dólares, dado por el propio proyecto GIMPS, pero no compite con el premio de la EFF (Electronic Frontier Foundation), que ofrece 150,000 dólares por el primer primo con al menos 100 millones de dígitos, y 250,000 dólares por descubrir el primer primo con al menos mil millones de dígitos.

primestamp

Es interesante hacer notar que desde el punto de vista de la programación, los números de Mersenne son muy simples. Por ejemplo, ensu forma binaria, los tres primeros son 11, 111, 11111, etcétera. En general, 2n-1 es simplemente un número binario con n unos. El hecho es que tenemos primos de Mersenne para n=31, 61 y 127 y frecuentemente son muy útiles cuando se necesita un primo rápidamente.

Finalmente, ¿cuáles son todas las cifras del primo 48 de Mersenne? En erl sitio Programming Praxis se reta a los lectores (programadores) a que generen los 17 millones de dígitos. Un programa simple en C no puede hacer esto porque los tipos de los enteros tienen limitaciones evidentes. Pero tal vez usando una biblioteca de números muy grandes, como la Multiple Precision Library de GNU podría ser de gran ayuda.

Haciéndome eco a este concurso, a las tres primeras soluciones completas y verificables (incluyendo el código fuente), de los lectores de unocero, se hará acreedores a mi colección de libros de Sudoku (y uno de ajedrez). Cuatro libritos en total.

Referencias:

GIMPS
Programming Praxis

Reacciones 0

Manuel López Michelone. Físico por la UNAM y Maestro en Ciencias por la Universidad de Essex en el tema de Inteligencia Artificial. Columnista por muchos años en publicaciones de la industria del cómputo y ávido programador. @morsa.

También te puede interesar

Comentarios

  • bezeoner

    Muy interesante, le voy a hablar de esto a mi profesora de matemáticas. Haber si me sube la nota.

    • Don_Ramón

      Dijo el Profesor Jirafales:Ahora vamos a buscar el area del triangulo…
      Don Ramón que se había metido al salón huyendo de Doña Florinda reviró: Pues que todavía no la encuentran?, si desde que yo era niño la nadan buscando….

  • http://www.rockodev.com/ RockoDev

    Estuve haciendo varios intentos, los dos primeros no tengo idea si funcionaban, los deje ejecutandose un rato y nada…

    En fin, creo que tengo 2 soluciones (en Python):
    https://gist.github.com/RockoDev/4747810
    https://gist.github.com/RockoDev/4747815

    La primera solo funciona con números pequeños y la segunda no la he probado completamente (sigue ejecutandose).

    Estaria bien que de vez en cuando publiquen retos de programación en el sitio, como programación lúdica. Pero que no tarden tanto en ejecutarse jeje.

    • morsa

      Rocko,

      no soy experto en python pero no puedes usar float, no vas a poder imprimir todas las cifras (17 millones de dígitos). No caben en los tipos tradicionales. Necesitas usar un arreglo dinámico para poner las potencias de 2 a calcular. Sugiero una estructura dinámica (dobles listas ligadas), o usar una biblioteca para manejar números con infinita precisión. Otra opción es usar mathematica o mumath.

      • http://www.rockodev.com/ RockoDev

        Eso es para calcular solo el porcentaje del progreso, pero ya lo cambié de float a long.
        Leeré un poco sobre las librerías que menciona, creo que GMP tambien se puede usar con Python.

      • http://www.rockodev.com/ RockoDev

        Volvi a actualizar el código. Aparentemente ya funciona bien en Python 2.7.
        https://gist.github.com/RockoDev/4747810

        Mañana lo pondré a correr, espero que no tarde más de unas horas jeje

  • Ricardo Torres

    Muy interesante y el reto más! (y no es gool!!)

    Al revisar toda la info pues ya varios se han puesto manos a la obra y veo que la librería GMP es de las más optimizadas, además soy fan de python, así que veamos.

    En python existe la librería gmpy y en mi intento por instalarla usando pip ha sido toda una odisea instalando dependencias de desarrollo… hummm!

    Pero hoooo en mi distro de Linux existe el paquete python-gmpy, así que me ha simplificado el trabajo, ahora sólo resta abrir el iptyhon y ejecutar las siguientes líneas:
    — ipython
    import gmpy

    elmayorprimo = gmpy.mpz(2**57885161 – 1) #sólo ha tardado unos segundos

    salida = open(“thebiggestprime.txt”,”w”) #el resultado se guarda en un archivo txt

    salida.write(str(elmayorprimo)) # hay que convertir el tipo mpz a string, esto se tardó un poco más!
    salida.close()

    Ahora desde una sesión de bash ejecuto el comando:
    — bash
    $ wc thebiggestprime.txt
    0 1 17425170 thebiggestprime.txt

    $

    Osea que el archivo tiene exactamente la cantidad de caracteres o podría decir dígitos de longitud que se espera debe tener el número primo.

    Además por razones obvias, el archivo tiene un tamaño aproximado de 17M, así que si alguien lo quiere consultar pongo a disposición el archivo en txt (17MB) y en zip (8MB).

    https://dl.dropbox.com/u/2285312/thebiggestprime.txt (txt)

    https://dl.dropbox.com/u/2285312/thebiggestprime.zip (zip)

    Mucho OJO: Si abren el txt puede que su navegador de quede congelado o su pc o su corazón, así que mejor bajen el zip.

    Salu2+
    RT

  • http://www.facebook.com/profile.php?id=100002901454005 Miguel Pérez

    Muy interesante. Yo he escrito el programa en C haciendo uso de la librería GMP. El programa no tarda más que unos pocos segundos en obtener el resultado e imprimirlo en un archivo de texto. Adicional mente el programa muestra este número en fragmentos para que pueda ser visible sin necesidad de abrir el archivo de 17 MB apróx. resultado del cálculo.

    Les dejo este link con una carpeta ZIP que contiene el código fuente, el ejecutable (en linux) y el archivo de 17MB que contiene el número en cuestión.

    Código fuente: http://enginetec.com.mx/NumeroPrimo/mersenne.cpp
    Archivo ZIP: http://enginetec.com.mx/NumeroPrimo/NumeroPrimo.zip

    Saludos!

  • http://www.facebook.com/profile.php?id=699833897 Eleazar Prieto

    Veo que en el concurso local ya hubo quienes descifraron los 17 millones de dígitos ahora solo falta comprobar si es el numero correcto …. pueden comparar cifra por cifra o ver si ese numero es primo creo que eso tomara un poco mas de tiempo ……..

    Ya entonados por que no buscar 2^(2^57,885,161 – 1) – 1 ….. que seguramente es un numero primo y de mas de 100 millones de dígitos y se ganan una buena lana….

    • Ricardo Torres

      El problema de esto esa pequeña parte de “seguramente es un primo” lo que tendríamos que cambiarlo por un “es un primo” y en lo que escribo esto ya estoy calculando el número indicado y estoy esperando a que termine para compartir el número de cifras que tiene… esperando… huuuuu! será que estoy calculando otra lista de número primos (ya me envicié!) que encontrar los dígitos de este número me ha puesto todo muy lento, así que será para cuando termine el otro proceso o si alguien lo encuentra antes que nos diga cuantos dígitos tiene ;)

      Salu2+

      • http://www.facebook.com/profile.php?id=699833897 Eleazar Prieto

        Bien nos cuentas como te fue…. recuerda que estas dando el salto de calcular una potencia de 7 dígitos (57,885,161) a una de 17 millones de dígitos…. creo que me sentare a esperar tu resultado

  • morsa

    A reserva de revisar con cuidado las respuestas, al menos ya hay dos ganadores… Miguel Pérez y Ricardo Torres. Un tercer ganador sería RockoDev. Me da gusto que el reto haya surtido efecto y en estos días les estoy mandando los libritos.

    saludos
    Manuel

  • http://www.rockodev.com/ RockoDev

    Listo. Ya logré obtener las 17 millones de cifras.
    Como Ricardo Torres ya lo hizo en Python, decidí hacerlo en PHP.
    https://gist.github.com/RockoDev/4751046
    http://php.net/manual/es/book.gmp.php
    Solo hay que habilitar la libreria y aumentar el limite de memoria en el php.ini

    • Ricardo Torres

      Muy bien por esa versatilidad en lenguajes y a cuanto has tenido que aumentar el límite de memoria?

      Salu2+

      • http://www.rockodev.com/ RockoDev

        Solo le quité el limite jeje.

  • Clein

    =O que lastima leerlo tarde, muchas gracias morsa por el concurso y por todo ^^

  • morsa

    Miguel Pérez, Ricardo Torres y RockoDev son los ganadores de los libritos. La semana que viene se los hago llegar. Mánden un correo a morsa@la-morsa.com con sus datos. Pongan sus teléfonos para confirmar que son quienes dicen que son.

    saludos y felicidades. Buen trabajo!

  • morsa

    Miguel Pérez, Ricardo Torres y RockoDev, escríbanme con sus datos para hacerles llegar sus premios: morsa@la-morsa.com

Forma parte de nuestra comunidad en Facebook.

Danos Like y entérate de mucho más.