Numero primo di Mersenne

Da Wikipedia, l'enciclopedia libera.

In matematica un numero primo di Mersenne è un numero primo esprimibile come:

M_p = 2^p - 1

con p intero positivo primo. Tale numero p è talvolta indicato come esponente di Mersenne (successione A000043 in OEIS). Si noti che 2^{11} - 1 = 2047 = 23 \cdot 89 non è primo e che quindi non tutti i numeri primi corrispondono a un esponente di Mersenne, ma solo quelli per cui M_p = 2^p - 1 risulta anch'esso primo.

A volte nella definizione di numero primo di Mersenne M_n non viene richiesto a priori che l'indice n sia primo. L'equivalenza delle due definizioni segue dal fatto che se  M_n è primo, allora anche n deve essere primo, come si vede facilmente dall'identità

 \begin{align}2^{ab}-1&=(2^a-1)\cdot \left(1+2^a+2^{2a}+2^{3a}+\cdots+2^{(b-1)a}\right)\\&\end{align}

In generale un numero del tipo M_n = 2^n - 1 viene detto "numero di Mersenne" (anche quando non è un numero primo di Mersenne). Si conoscono diverse proprietà dei fattori primi degli M_p composti con p primo. Ad esempio (e Fermat fu il primo ad evidenziare e usare questa proprietà) si può dimostrare che ogni fattore primo di M_p dev'essere del tipo 2kp+1 con k intero positivo[1].

I numeri primi di Mersenne prendono il nome dal matematico francese Marin Mersenne (1588-1648). Mersenne compilò una lista di numeri primi di questo tipo considerando tutti i valori di n fino a n=257. Tale lista conteneva però alcuni errori: includeva M_{67} e M_{257} (che non sono primi), mentre non comparivano M_{61}, M_{89} e M_{107} (che sono primi).

I primi dodici numeri primi di Mersenne sono:

 M_2 = 2^2 - 1 = 3
 M_3 = 2^3 - 1 = 7
 M_5 = 2^5 - 1 = 31
 M_7 = 2^7 - 1 = 127
 M_{13} = 2^{13} - 1 = 8191
 M_{17}=131071
 M_{19}=524287
 M_{31}=2147483647
 M_{61}=2305843009213693951
 M_{89}=618970019642690137449562111
 M_{107}=162259276829213363391578010288127
 M_{127}=170141183460469231731687303715884105727

I numeri primi di Mersenne sono collegati con i numeri perfetti. Nel IV secolo a.C. Euclide dimostrò che se M_n è un numero primo, allora {M_n\cdot(M_n+1) \over 2} = 2^{n-1}\cdot(2^n - 1) è un numero perfetto.

Nel XVIII secolo Eulero provò che tutti i numeri perfetti pari hanno questa forma. Nessun numero perfetto dispari è conosciuto, ed è anche possibile che non ne esistano.

L'avvento dei calcolatori elettronici ha notevolmente accelerato la scoperta dei primi di Mersenne. I primi dodici numeri primi di Mersenne sono stati scoperti prima del XX secolo. Alla fine del millennio i primi di Mersenne conosciuti erano 38; oggi invece se ne conoscono 48 e i tredici più recenti sono stati scoperti nell'ambito della GIMPS, la Great Internet Mersenne Prime Search, iniziativa che sfrutta le risorse disponibili di migliaia di computer in rete per cercare i primi di Mersenne. Il test di primalità usato dal GIMPS è il test di Lucas - Lehmer.

In assoluto, i record dei più grandi numeri primi conosciuti sono ormai da tempo dei numeri primi di Mersenne. Ciò è dovuto principalmente al fatto che per tali numeri è possibile usare un test di primalità ad hoc (il test di Lucas-Lermer) che è molto più veloce degli altri tipi di test di primalità. Il più grande numero primo conosciuto (a novembre 2014) è  M_{57885161}. Ha più di 17 milioni di cifre ed è stato anch'esso trovato nell'ambito della GIMPS:

 M_{57885161}=2^{57 885 161} - 1

Se scritti in base 2, tutti i numeri primi di Mersenne sono primi repunit, ovvero sono rappresentati da stringhe di p cifre unitarie, dove p è l'esponente primo di Mersenne. Negli esempi qui di seguito l'indice denota la base in cui il numero viene espresso:

310 = 112
710 = 1112
3110 = 111112
12710 = 11111112
819110 = 11111111111112.

I primi di Mersenne sono anche primi palindromi e primi permutabili.

Lista numeri primi di Mersenne[modifica | modifica wikitesto]

# n Mn Cifre in Mn Data scoperta Scopritore
1 2 3 1 Antichità Ignoto
2 3 7 1 Antichità Ignoto
3 5 31 2 Antichità Ignoto
4 7 127 3 Antichità Ignoto
5 13 8191 4 1456 Ignoto
6 17 131071 6 1588 Cataldi
7 19 524287 6 1588 Cataldi
8 31 2147483647 10 1772 Eulero
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 gennaio 1952 Robinson
14 607 531137992…031728127 183 30 gennaio 1952 Robinson
15 1.279 104079321…168729087 386 25 giugno 1952 Robinson
16 2.203 147597991…697771007 664 7 ottobre 1952 Robinson
17 2.281 446087557…132836351 687 9 ottobre 1952 Robinson
18 3.217 259117086…909315071 969 8 settembre 1957 Riesel
19 4.253 190797007…350484991 1281 3 novembre 1961 Hurwitz
20 4.423 285542542…608580607 1.332 3 novembre 1961 Hurwitz
21 9.689 478220278…225754111 2.917 11 maggio 1963 Gillies
22 9.941 346088282…789463551 2.993 16 maggio 1963 Gillies
23 11.213 281411201…696392191 3.376 2 giugno 1963 Gillies
24 19.937 431542479…968041471 6.002 4 marzo 1971 Tuckerman
25 21.701 448679166…511882751 6.533 30 ottobre 1978 Noll e Nickel
26 23.209 402874115…779264511 6.987 9 febbraio 1979 Noll
27 44.497 854509824…011228671 13.395 8 aprile 1979 Nelson e Slowinski
28 86.243 536927995…433438207 25.962 25 settembre 1982 Slowinski
29 110.503 521928313…465515007 33.265 28 gennaio 1988 Colquitt e Welsh
30 132.049 512740276…730061311 39.751 20 settembre 1983 Slowinski
31 216.091 746093103…815528447 65.050 6 settembre 1985 Slowinski
32 756.839 174135906…544677887 227.832 19 febbraio 1992 Slowinski e Gage in Harwell Lab Cray-2
33 859.433 129498125…500142591 258 716 10 gennaio 1994 Slowinski e Gage
34 1.257.787 412245773…089366527 378.632 3 settembre 1996 Slowinski e Gage
35 1.398.269 814717564…451315711 420.921 13 novembre 1996 GIMPS / Joel Armengaud (PC Pentium 90)
36 2.976.221 623340076…729201151 895.932 24 agosto 1997 GIMPS / Gordon Spence (PC Pentium 100)
37 3.021.377 127411683…024694271 909.526 27 gennaio 1998 GIMPS / Roland Clarkson (Pentium 200)
38 6.972.593 437075744…924193791 2.098.960 1º giugno 1999 GIMPS / Nayan Hajratwala (Pentium II 350)
39 13.466.917 924947738…256259071 4.053.946 14 novembre 2001 GIMPS / Michael Cameron (800 MHz AMD T-Bird PC)
40 20.996.011 125976895…855682047 6.320.430 17 novembre 2003 GIMPS / Michael Shafer (2 GHz Pentium 4 Dell Dimension PC)
41 24.036.583 299410429…733969407 7.235.733 15 maggio 2004 GIMPS / Josh Findley (2.4 GHz Pentium 4 Windows XP PC)
42 25.964.951 122164630…577077247 7.816.230 18 febbraio 2005 GIMPS / Martin Nowak (2.4 GHz Pentium 4 Windows XP PC)
43 30.402.457 315416475…652943871 9.152.052 15 dicembre 2005 GIMPS / Curtis Cooper e Steven Boone
44 32.582.657 124575026…053967871 9.808.358 4 settembre 2006 GIMPS / Curtis Cooper e Steven Boone
45[2] 37.156.667 202254406…308220927 11.185.272 6 settembre 2008 GIMPS / Hans-Michael Elvenich, George Woltman, Scott Kurowski et al
46[2] 42.643.801 169873516…562314751 12.837.064 12 aprile 2009 GIMPS / Odd M. Strindmo
47[2] 43.112.609 316470269…697152511 12.978.189 23 agosto 2008 GIMPS / Edson Smith, George Woltman, Scott Kurowski et al
48[2] 57.885.161 581887266…724285951 17.425.170 25 gennaio 2013 GIMPS / Curtis Cooper, George Woltman, Scott Kurowski et al

Note[modifica | modifica wikitesto]

  1. ^ http://www.bitman.name/math/article/288
  2. ^ a b c d Non è noto se esistano altri numeri primi di Mersenne tra il 44° (M32582657) e il 48° (M57885161) e la numerazione della tabella è pertanto provvisoria nella sua parte finale. I numeri primi di Mersenne non sono sempre stati scoperti in ordine crescente. Ad esempio, il 29° primo di Mersenne è stato scoperto dopo il 30° e il 31°. Allo stesso modo il 47° è stato seguito da altri due numeri più piccoli, uno scoperto due settimane più tardi e l'altro 8 mesi dopo. GIMPS Milestones Report. URL consultato l'8 Novembre 2014.

Voci correlate[modifica | modifica wikitesto]

Altri progetti[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica