Pero a partir del domingo por la tarde, a la caza de un primo grande. Aviso que no va a ser el más grande. Nos conformaremos con alguno que haya sido considerado muy grande en el pasado.
¿Cómo lo vamos a hacer?
Primero ir a la web que mejor información tiene sobre esta cosas. Además parece que hay un montón de locos que se dedican a publicar en este sitio los primos más grandes conocidos que van obteniendo. El sitio es este: http://primes.utm.edu/notes/by_year.html#table2.
En el enlace concreto que he puesto aparecen los primos más grandes descubiertos a lo largo de la historia.
1.-Antes de la era de las computadoras.
Desde antes de las computadoras los números de Mersenne (amigo de Fermat) han tenido gran importancia. Al principio hubo un error histórico consistente en pensar que todos los números de Mersenne eran primos. Muchos si, y era un buen método para obtener primos grandes, pero no todos.
En la Wikipedia tenemos la definición de “número primo de Mersenne”. Cuidado, se refiere a aquellos números de Mersenne que son primos porque todos no lo son.
También conviene leer su biografía.
Voy a tirar de un librito de matemáticas para centrarnos más…
En el año 1644 el monje francés Marin Mersenne publica “Cogitata Physica-Mathematica” en el que afirma que los números Mn = (2 ^ n) -1 son primos para 2,3,5,7,13,17,19,31,67,127,257 y son compuestos para el resto de valores de n menores que 257.
En 1947 se descubrió que M67 y M257 no son primos. Y también que M61, M89 y M107 si lo eran. Esto es lo de menos.
Algunos pensaron que Mn es primo siempre que n sea primo pero fallaron porque por ejemplo M11 no es primo.
Otros han pensado que Mn es primo cuando n sea un número de Mersenne, pero tampoco funciona porque cuando se llega a M13 falla.
2.-En la era de la electrónica.
Aquí es donde estamos. La lista de primos grandes que nos muestran empieza en 1951 y llega al 2006. Vemos que casi todos son números de Mersenne.
¿Qué tienen de especial estos números?
En esta página http://primes.utm.edu/prove/prove3_2.html#test nos dan la explicación matemática que nos aseguran que es muy ¿divertida? A mi en estos momentos me supera así que prefiero no seguir por aquí. Si que nos quedamos con algo muy importante: All of the Mersenne records were found using the Lucas-Lehmer test.
Ahora buscamos ese test en Wikipedia que nos lo explicará de forma muy sencilla: http://es.wikipedia.org/wiki/Test_de_Lucas-Lehmer
De todas formas el test tal y como viene es lioso porque no se ven los números de Mersenne.
Entonces vemos que hay una entrada más apropiada con nombre "Test de Lucas-Lehmer para números de Mersenne":
http://es.wikipedia.org/wiki/Test_de_Lucas-Lehmer_para_n%C3%BAmeros_de_Mersenne
Ahora ya lo vemos todo más claro. Hay que generar una sucesión.
Los primeros términos de esta sucesión son 4, 14, 194, 37634, ...
En un sitio llamado OEIS (The On-Line Encyclopedia of Integer Sequences) identifican la secuencia como "A003010": http://www.research.att.com/~njas/sequences/A003010
Al final lo que tenemos es lo siguiente:
Lo que haremos es esto:
- Buscar un Mn grande con ayuda de algún método de exponenciación binaria.
- Comprobar si Mn es primo calculando previamente la secuencia para n-2.
Nota: Si hay un campeón que quiera comprobar la demostración del test de Lucas-Lehmer que haga clic aquí
2 comentarios:
Hola de nuevo! he visto que has pasado a C++ (esa opción siempre es buena) pero antes probaste a usar el mismo sistema en VB? en lugar de sacar el resultado por pantalla guardarlo en un fichero es siempre muchísimo más rápido.
Saludos!
Hola tayoken,
Estoy en ello, el fin de semana ha sido intenso.
Acabo de convertir las líneas de C++ a VB.
He lanzado hace un par de minutos el programita hasta el límite de 100 millones. A ver que pasa. Escribo un post con el resultado.
Saludos.
Publicar un comentario