Primos de Mersenne

Descargar el notebook

Pierre de Mersenne fue un filósofo del siglo XVII que en su obra Cognitata Physico-Mathematica enunció una serie de afirmaciones sobre teoría de números.

Un número de Mersenne es de la forma M(n)= 2^n-1 para n un número natural, y es un primo de Mersenne si su resultado es un número primo, es necesario más no suficiente que n sea un número primo. Mersenne realizó una lista con exponentes hasta 257 de los que el conjeturó eran todos los primos de Mersenne que existían. Esta lista tenía errores pues incluyó a  M(67) y M(257) que son compuestos y excluyó a M(61), M(89) y M(107) que son primos.

Hasta enero de 2016 se conocen 49 primos de Mersenne, siendo el último

M(74207281)

un número de más de veintidós millones de cifras.

La actual conocida como Conjetura de Mersenne es :

Existen infinitos números primos de la forma 2^n-1

Si n es un número compuesto también 2^n-1 es compuesto, luego realizaremos la búsqueda entre los primos n buscando primos de Mersenne.

Para optimizar los tiempos de ejecución, utilizaré la orden ParallelelDo que hace que se aprovechen al máximo los diferentes núcleos del computador dividiendo las tareas, así se hace necesario acompañarla de la orden SetSharedVariable para distribuir las variables entre los núcleos, la orden AbsoluteTiming nos muestra el tiempo en segundos de ejecución.

mers = {};

SetSharedVariable[mers];

AbsoluteTiming[
 ParallelDo[If[PrimeQ[2^n - 1], AppendTo[mers, n]], {n, 10000}]; mers]

{126.061473, {1, 1, 1, 1, 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521,607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 2, 3, 89, 5,107, 7, 13, 17, 127, 19, 31, 61, 521, 607, 2, 3, 5, 7, 521, 13, 17, 19, 31,607, 61, 89, 107, 127, 1279, 2281, 2203, 3217, 4253, 4423, 9689, 9941}}

DeleteDuplicates[mers]

{1, 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281,3217, 4253, 4423, 9689, 9941, 11213}

Length[DeleteDuplicates[mers]]

24

Estos son los primeros 24 primos de Mersenne.

mersenne = Table[2^n - 1, {n, mers}]

Con una longitud en cifras de:

IntegerLength[mersenne]

{1, 1, 2, 3, 4, 6, 6, 10, 19, 27, 33, 39, 157, 183, 386, 664, 687, 969, 1281,1332, 2917, 2993}

Otra forma de determinación es:

mersenneprimeQ[n_Integer] := PrimeQ[2^n - 1]

DistributeDefinitions[mersenneprimeQ]

SetSharedVariable[mersenneprimeQ]

AbsoluteTiming[Parallelize[Select[Range[10000], mersenneprimeQ]]]

{68.971097, {2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279,2203, 2281, 3217, 4253, 4423, 9689, 9941}}

AbsoluteTiming[Select[Range[10000], mersenneprimeQ]]

{130.129557, {2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279,2203, 2281, 3217, 4253, 4423, 9689, 9941}}

Así, M(2), M(3),..., M(9689), M(9941) son primos de Mersenne.

Otra forma más :

Parallelize[Select[Range[9000, 10000], PrimeQ[2^# - 1] &],
 Method -> "FinestGrained"]

{9689, 9941}

Así, M(9689) y M(9941), son primos de Mersenne.

Propuesta

Buscar los primos de Mersenne 23,24 y 25.

Referencias

Wikipedia