Numero primo di Mersenne: differenze tra le versioni
mNessun oggetto della modifica |
fix |
||
Riga 3: | Riga 3: | ||
<math>M_p = 2^p - 1</math> |
<math>M_p = 2^p - 1</math> |
||
con <math>p</math> [[Numero intero|intero positivo]] primo. Tale numero <math>p</math> è talvolta indicato come ''esponente di Mersenne'' (successione [[oeis:A000043|A000043]] in [[OEIS]]). Si noti che <math>2^{11} = 2047 = 23 \cdot 89</math> non è primo e che quindi non tutti i numeri primi corrispondono a un esponente di Mersenne, ma solo quelli per cui <math>M_p = 2^p - 1</math> risulta anch'esso primo. |
con <math>p</math> [[Numero intero|intero positivo]] primo. Tale numero <math>p</math> è talvolta indicato come ''esponente di Mersenne'' (successione [[oeis:A000043|A000043]] in [[OEIS]]). Si noti che <math>2^{11} - 1 = 2047 = 23 \cdot 89</math> non è primo e che quindi non tutti i numeri primi corrispondono a un esponente di Mersenne, ma solo quelli per cui <math>M_p = 2^p - 1</math> risulta anch'esso primo. |
||
A volte nella definizione di numero primo di Mersenne <math>M_n</math> non viene richiesto a priori che l'indice <math>n</math> sia primo. L'equivalenza delle due definizioni segue dal fatto che se <math> M_n </math> è primo, allora anche <math>n</math> deve essere primo, come si vede facilmente dall'identità |
A volte nella definizione di numero primo di Mersenne <math>M_n</math> non viene richiesto a priori che l'indice <math>n</math> sia primo. L'equivalenza delle due definizioni segue dal fatto che se <math> M_n </math> è primo, allora anche <math>n</math> deve essere primo, come si vede facilmente dall'identità |
||
Riga 34: | Riga 34: | ||
L'avvento dei [[Computer|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]]. |
L'avvento dei [[Computer|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 |
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) è <math> M_{57885161}</math>. Ha più di 17 milioni di cifre ed è stato anch'esso trovato nell'ambito della GIMPS: |
||
:<math> M_{57885161}=2^{57 885 161} - 1</math> |
:<math> M_{57885161}=2^{57 885 161} - 1</math> |
||
Versione delle 16:50, 10 dic 2014
In matematica un numero primo di Mersenne è un numero primo esprimibile come:
con intero positivo primo. Tale numero è talvolta indicato come esponente di Mersenne (successione A000043 in OEIS). Si noti che non è primo e che quindi non tutti i numeri primi corrispondono a un esponente di Mersenne, ma solo quelli per cui risulta anch'esso primo.
A volte nella definizione di numero primo di Mersenne non viene richiesto a priori che l'indice sia primo. L'equivalenza delle due definizioni segue dal fatto che se è primo, allora anche deve essere primo, come si vede facilmente dall'identità
In generale un numero del tipo viene detto "numero di Mersenne" (anche quando non è un numero primo di Mersenne). Si conoscono diverse proprietà dei fattori primi degli composti con primo. Ad esempio (e Fermat fu il primo ad evidenziare e usare questa proprietà) si può dimostrare che ogni fattore primo di dev'essere del tipo con 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 fino a . Tale lista conteneva però alcuni errori: includeva e (che non sono primi), mentre non comparivano , e (che sono primi).
I primi dodici numeri primi di Mersenne sono:
I numeri primi di Mersenne sono collegati con i numeri perfetti. Nel IV secolo a.C. Euclide dimostrò che se è un numero primo, allora è 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) è . Ha più di 17 milioni di cifre ed è stato anch'esso trovato nell'ambito della GIMPS:
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
# | 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
- ^ http://www.bitman.name/math/article/288
- ^ 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, su mersenne.org. URL consultato l'8 Novembre 2014.
Voci correlate
- Numero perfetto
- Numero primo
- Numero primo di Fermat
- Nuova congettura di Mersenne
- Costante di Erdős-Borwein
- Potenza di due
- The Prime Pages
Altri progetti
- Wikinotizie contiene l'articolo Scoperti i due nuovi numeri primi più grandi a distanza di pochi giorni, 18 settembre 2008
Collegamenti esterni
- (EN) The Great Internet Mersenne Prime Search
- (EN) Storia su The Prime Pages
- (EN) Successione A000668 in [[OEIS]]
- (EN) Pagina contenente il numero primo più grande (pagina di 22 MB, aprire solo con connessioni più veloci)