Números de Mersenne

Si recuerdan, hace un tiempo escribí un artículo sobre números primos. Pues bien, hoy les traigo un subgrupo de estos, los números de Mersenne.

Los números de Mersenne son los números con formato 2ⁿ-1 con n primo y los números primos de Mersenne son los números primos que tienen ese formato. Tal vez esto así parezca algo totalmente carente de utilidad, pero hay mucho detrás de estos números.

Un poco de historia. Fuera de Mersenne.

Muchos escritores antiguos creían que el formato 2ⁿ-1 eran primos para todo n primo. Pero en 1536 Hudalricus Regius mostró que 2¹¹-1 no era primo (2047). En 1603 Pietro Cataldi verificó 2¹⁷ -1 y 2¹⁹-1 como primo, pero de manera incorrecta dijo que para n 23,29,31 y 37 también lo era. En 1640 Fermat demostró que Cataldi estaba equivocado para 23 y 37. En 1738 Euler demostró que Cataldi estaba equivocado acerca del 29, pero un tiempo después mostró que el 31 era correcto.

Y un día apareció Mersenne.

Mersenne nació de una familia de campesinos cerca de Oizé en la provincia de Maine (Francia). Estudió en la universidad de La Flèche donde se hizo amigo de René Descartes. Se dedicó a la teología y al estudio del hebreo. También se dedicó a enseñar filosofía y teología pero a su regreso a París en 1620 en el convento de L’Annonciade y en companía de gente como Descartes, Étienne Pascal, Gilles de Robeval y Nicholas-Claude Fabri de Peiresc, estudió matemáticas y música (parece que en esa época la gente tenía un espectro más amplio a la hora del estudio). También anduvo a las cartas con tipos como Pierre de Fermat, Galileo Galilei, Giovanni Doni y Constantijn Huygens.

Le dedicó mucho a escribir sobre filosofía y teología, pero lo que trae a este personaje al blog es la matemática. Probablemente este hombre fue finalmente famoso por los números que llevan su nombre. Mersenne traje a estos números en Cognitata physico-mathematica de 1641 donde conjeturó algunas propiedades sobre ellos, algunas de estas propiedades sólo pudieron ser comprobadas o refutadas ya en el siglo XX.

La era moderna

Con la aparición de métodos cada vez más rápidos para calcular los números de Mersenne fueron apareciendo, y de hecho son los números primos más grandes que se conocen (es más sencillo verificar por el test de Lucas-Lehmer, un tema que trataremos en algún momento). De hecho apareció hasta una asociación de cómputo de números primos de Mersenne que inclusive distribuye premios en efectivo.

Actualmente el número primo de Mersenne más grande conocido (el número 48 que se conoce con estas propiedades) es el 2^57,885,161-1 que nos da un enorme número de más de 17 millones de dígitos (en ese link tienen una versión resumida del número y un link para bajarlo entero).

Un poco de programación

Basandome en el programa del post de números primos, armé este:

from datetime import *

def esPrimo(numero):
    primo=True
    if numero>3:
        if numero%2!=0 and numero%5!=0:
            for i in range(3,(numero-1)/2,2):
                if numero%i==0:
                    primo=False
                    break
        else:
            if numero==5:
                primo=True
            else:
                primo=False
    else:
        if numero<2
            primo=False
        else:
            primo=True
    return primo

n=input("Ingrese n: ")
numero=(2**n)-1
print datetime.today()
if esPrimo(numero)==True:
    print "El numero: "+str(numero)+" es primo"
else:
    print "El numero: "+str(numero)+" no es primo"
print datetime.today()

Con esto podemos probar algunos de los números que existen ya demostrados:

n=13 (quinto número primo de Mersenne): 8191 es primo (tardó 4 décimas en determinarlo).

n=17 (sexto número primo de Mersenne): 131071 es primo (tardó 6 décimas en determinarlo).

n=19 (séptimo número primo de Mersenne): 524287 es primo (tardó 14 décimas en determinarlo).

El programa parece que es lento para números donde n>29 por lo que el método que teníamos no va a ser bueno para número tan altos (y ni hablar que este justamente no es tan alto para lo que queremos ver (el octavo número de mersenne tiene n=31, es 2147483647, verificado en 1772 por Euler.

Próximamente, en esta sección de números primos iremos viendo métodos para calcular aún más rápido si un número es primo o no.

Fuentes:

GIMPS

The Prime Pages

Wikipedia -Marin Mersenne.