Nombre primer de Mersenne

De Viquipèdia
Dreceres ràpides: navegació, cerca

Un nombre primer de Mersenne és un nombre primer que és igual a una potència de 2 menys 1. Per exemple, 3 = 4 − 1 = 22 − 1 és un primer de Mersenne, igual que 7 = 8 − 1 = 23 − 1. En canvi, 15 = 16 − 1 = 24 − 1, per exemple, no és primer.

En general, doncs, els nombres primers de Mersenne són nombres primers de la forma:

Mn = 2n − 1.

Cal no confondre els nombres de Mersenne amb els nombres primers de Mersenne, que són els nombres de Mersenne que, a més a més, són primers.

Els primers de Mersenne tenen relació amb els nombres perfectes, aquells que són iguals a la suma dels seus divisors. Històricament, l'estudi dels primers de Mersenne fou motivat per aquesta relació. Al segle IV aC Euclides demostrà que si M és un primer de Mersenne llavors M(M + 1)/2 és un nombre perfecte. Dos mil anys més tard, al segle XVIII, Euler demostrà que tots els nombres parells perfectes són d'aquesta forma; no es coneixen nombres perfectes senars, i se sospita que no existeixen, però encara no disposa de cap demostració.

Actualment no se sap si hi ha un nombre infinit de nombres primers de Mersenne, però es té la sospita que la resposta és afirmativa i, de fet, és una part del contingut de la conjectura de Lenstra-Pomerance-Wagstaff.

Recerca de primers de Mersenne[modifica | modifica el codi]

El càlcul

(2^a-1)\cdot (1+2^a+2^{2a}+2^{3a}+\dots+2^{(b-1)a})=2^{ab}-1

demostra que Mn només pot ser primer si n també ho és, fet que simplifica considerablement la recerca de primers de Mersenne, però la inversa no és certa: Mn pot ser compost encara que n sigui primer. Per exemple, 211 − 1 = 23 · 89.

Es disposa d'algoritmes ràpids per trobar primers de Mersenne i per això els nombres primers més grans que es coneixen són primers de Mersenne.

Els primers quatre primers de Mersenne M2, M3, M5, M7 wja es coneixien a l'Antiguitat. El cinquè, M13, fou descobert abans del 1461; els dos següents, M17 i M19, els trobà Pietro Cataldi el 1588. El 1750 Euler verificà que M31 és primer. Els següents descoberts foren M127, el 1876, gràcies a Edouard Lucas, després M61 per Ivan Mikheevich Pervushin el 1883. Els darrers abans de l'aparició dels ordinadors foren M89 i M107, calculats per R. E. Powers el 1911 i el 1914, respectivament.

Fins al setembre de 2008, només es coneixien 46 primers de Mersenne; el nombre primer més gran que es coneix (257.885.161 − 1) és de Mersenne i fou descobert gràcies a un projecte de computació distribuïda a Internet, el 'Great Internet Mersenne Prime Search' (GIMPS).

Llista de primers de Mersenne[modifica | modifica el codi]

La taula següent mostra tots els primers de Mersenne coneguts fins a gener de 2013:

# n Mn Dígits de Mn Data de descobriment Descobridor
1 2 3 1 Antiguitat Antiguitat
2 3 7 1 Antiguitat Antiguitat
3 5 31 2 Antiguitat Antiguitat
4 7 127 3 Antiguitat Antiguitat
5 13 8191 4 1456 anònim
6 17 131071 6 1588 Cataldi
7 19 524287 6 1588 Cataldi
8 31 2147483647 10 1772 Euler
9 61 2305843009213693951 19 1883 Pervushin
10 89 618970019…449562111 27 1911 Powers
11 107 162259276…010288127 33 1914 Powers
12 127 170141183…884105727 39 1876 Lucas
13 521 686479766…115057151 157 30 de gener de 1952 Robinson
14 607 531137992…031728127 183 30 de gener de 1952 Robinson
15 1.279 104079321…168729087 386 25 de juny de 1952 Robinson
16 2.203 147597991…697771007 664 7 d'octubre de 1952 Robinson
17 2.281 446087557…132836351 687 9 d'octubre de 1952 Robinson
18 3.217 259117086…909315071 969 8 de setembre de 1957 Riesel
19 4.253 190797007…350484991 1.281 3 de novembre de 1961 Hurwitz
20 4.423 285542542…608580607 1.332 3 de novembre de 1961 Hurwitz
21 9.689 478220278…225754111 2.917 1 de maig de 1963 Gillies
22 9.941 346088282…789463551 2.993 16 de maig de 1963 Gillies
23 11.213 281411201…696392191 3.376 2 de juny de 1963 Gillies
24 19.937 431542479…968041471 6.002 4 de març de 1971 Tuckerman
25 21.701 448679166…511882751 6.533 30 d'octubre de 1978 Noll & Nickel
26 23.209 402874115…779264511 6.987 9 de febrer de 1979 Noll
27 44.497 854509824…011228671 13.395 8 d'abril de 1979 Nelson & Slowinski
28 86.243 536927995…433438207 25.962 25 de setembre de 1982 Slowinski
29 110.503 521928313…465515007 33.265 28 de gener de 1988 Colquitt & Welsh
30 132.049 512740276…730061311 39.751 20 de setembre de 1983 Slowinski
31 216.091 746093103…815528447 65.050 6 de setembre de 1985 Slowinski
32 756.839 174135906…544677887 227.832 19 de febrer de 1992 Slowinski & Gage
33 859.433 129498125…500142591 258.716 10 de gener de 1994 Slowinski & Gage
34 1.257.787 412245773…089366527 378.632 3 de setembre de 1996 Slowinski & Gage
35 1.398.269 814717564…451315711 420.921 13 de novembre de 1996 GIMPS / Joel Armengaud
36 2.976.221 623340076…729201151 895.932 24 d'agost de 1997 GIMPS / Gordon Spence
37 3.021.377 127411683…024694271 909.526 27 de gener de 1998 GIMPS / Roland Clarkson
38 6.972.593 437075744…924193791 2.098.960 1 de juny de 1999 GIMPS / Nayan Hajratwala
39 13.466.917 924947738…256259071 4.053.946 14 de novembre de 2001 GIMPS / Michael Cameron
40* 20.996.011 125976895…855682047 6.320.430 17 de novembre de 2003 GIMPS / Michael Shafer
41* 24.036.583 299410429…733969407 7.235.733 15 de maig de 2004 GIMPS / Josh Findley
42* 25.964.951 122164630…577077247 7.816.230 18 de febrer de 2005 GIMPS / Martin Nowak
43* 30.402.457 315416475…652943871 9.152.052 15 de desembre de 2005 GIMPS / Curtis Cooper & Steven Boone
44* 32.582.657 124575026…053967871 9.808.358 4 de setembre de 2006 GIMPS / Curtis Cooper & Steven Boone
45* 37.156.667 202254406…308220927 11.185.272 6 de setembre de 2008 GIMPS / Hans-Michael Elvenich
46* 42,643,801 169873516…562314751 12,837,064 12 d'abril de 2009 GIMPS / Odd M. Strindmo
47* 43,112,609 316470269…697152511 12,978,189 23 d'agost de 2008 GIMPS / Edson Smith
48* 57,885,161 581887266…724285951 17,425,170 25 de gener de 2013 GIMPS / Curtis Cooper
*No se sap si existeixen encara primer de Mersenne per descobrir entre el 39è (M13,466,917) i el 48è (M43,112,609).

Vegeu també[modifica | modifica el codi]