Nombre primer de Mersenne
Un nombre primer de Mersenne és una categoria dels nombres de Marsenne, definida com els nombres primers iguals a una potència de 2 menys 1 (nombre de Mersenne). Per exemple, 3 = 4 − 1 = 2² − 1 és un primer de Mersenne, igual que 7 = 8 − 1 = 23 − 1. En canvi, altres nombres que compleixin la fórmula però no siguin primers, no es consideren primers de Mersenne, com ara 15 = 16 − 1 = 24 − 1.
En general, doncs, els nombres primers de Mersenne són nombres primers de la forma:
- Mn = 2n − 1, essent Mn un nombre primer.
Aquests nombres prenen el seu nom del filòsof i matemàtic francès Marin Mersenne, qui els definí al segle XVII. Cal no confondre els nombres de Mersenne amb els nombres primers de Mersenne.
Història i desenvolupament
[modifica]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 una potència de 2 menys 1 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 s'hi 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]El càlcul:
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'algorismes ràpids per a 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 M₂, M₃, M₅, M₇ ja es coneixien en 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 del 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]La taula següent mostra tots els primers de Mersenne coneguts fins l'octubre de 2016:
# 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 49* 74.207.281 300376418…086436351 22.338.618 7 de gener de 2016 GIMPS / Curtis Cooper 50* 77.232.917 467333183…762179071 23.249.425 26 de desembre de 2017 GIMPS / Jonathan Pace 51* 82.589.933 148894445…217902591 24.862.048 7 de desembre de 2018 GIMPS / Patrick Laroche
- * No se sap si queden per descobrir primers de Mersenne entre el 47è (M43.112.609) i el 51è (M82.589.933).