Numero primo di Mersenne
In matematica un numero primo di Mersenne è un numero primo inferiore di uno rispetto ad una potenza di due. I numeri primi di Mersenne sono esprimibili come:
con intero positivo primo; infatti, si può dimostrare che se non è primo, allora non è 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 51 e i diciassette 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 che è molto più veloce dei test generici a parità di ordine di grandezza nel numero; ecco perché in assoluto i record dei più grandi numeri primi conosciuti sono ormai da tempo dei numeri primi di Mersenne. Il più grande numero primo conosciuto (al 21 dicembre 2018) è . Ha più di 24 milioni di cifre decimali ed è stato anch'esso trovato nell'ambito GIMPS:
- [2]
Se scritti in base 2, tutti i numeri primi di Mersenne sono repunit primi, 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.
Si noti che questa proprietà è posseduta quando si sottrae 1 da tutte le potenze di 2 aventi per esponente un numero primo. In sostanza tutti i candidati a essere numeri primi di Mersenne (chiamati come detto sopra semplicemente "numeri di Mersenne") in notazione binaria sono primi repunit.
Si può osservare scorrendo la lista più sotto, che a parte il 3, tutti i numeri primi di Mersenne terminano con 1 o con 7. Questo è dovuto al fatto che le potenze di 2 terminano ciclicamente per 2, 4, 8, 6, quando l'esponente è rispettivamente della forma 1+4k, 2+4k, 3+4k e 4+4k (k numero naturale positivo). Per questa ragione soltanto le potenze di 2 terminanti per 2 e 8 hanno esponenti della forma 1+4k e 3+4k, ovvero hanno esponenti dispari, mentre quelle terminanti per 4 e 6 hanno esponenti pari. Dato infine, che in un numero primo di Mersenne , deve essere numero primo, questo deve essere dispari tranne nel caso di corrispondente all'unico numero di Mersenne terminante con 3 (il numero 3 appunto).
I primi di Mersenne, scritti in base 2, sono anche primi palindromi, primi permutabili e primi di Gauss.
Lista numeri primi di Mersenne
# | p | Mp | Cifre in Mp | 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 | 618970019642690137449562111 | 27 | 1911 | Powers |
11 | 107 | 162259276829213363391578010288127 | 33 | 1914 | Powers |
12 | 127 | 170141183460469231731687303715884105727 | 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 | 37.156.667 | 202254406…308220927 | 11.185.272 | 6 settembre 2008 | GIMPS / Hans-Michael Elvenich, George Woltman, Scott Kurowski et al |
46 | 42.643.801 | 169873516…562314751 | 12.837.064 | 12 aprile 2009 | GIMPS / Odd M. Strindmo |
47 | 43.112.609 | 316470269…697152511 | 12.978.189 | 23 agosto 2008 | GIMPS / Edson Smith, George Woltman, Scott Kurowski et al |
48 | 57.885.161 | 581887266…724285951 | 17.425.170 | 25 gennaio 2013 | GIMPS / Curtis Cooper, George Woltman, Scott Kurowski et al |
49?[3] | 74.207.281 | 300376418084…391086436351 | 22.338.618 | 7 gennaio 2016 | GIMPS / Curtis Cooper |
50?[3] | 77.232.917 | 467333183359…069762179071 | 23.249.425 | 26 dicembre 2017 | GIMPS / Jonathan Pace |
51?[3] | 82.589.933 | 148894445742…325217902591 | 24.862.048 | 7 dicembre 2018 | GIMPS / Patrick Laroche |
Note
- ^ Mauro Fiorentini - Mersenne (numeri di)
- ^ GIMPS Milestones Report, su mersenne.org. URL consultato il 21 dicembre 2018.
- ^ a b c Non è noto se esistano altri numeri primi di Mersenne tra il 48° (M57885161) e il 51° (M82589933) 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 il 2 giugno 2022.
Voci correlate
- Numero perfetto
- Numero primo
- Numero primo di Fermat
- Nuova congettura di Mersenne
- Costante di Erdős-Borwein
- Teorema di Euclide-Eulero
- 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) William L. Hosch, Mersenne prime, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
- (EN) Eric W. Weisstein, Numero primo di Mersenne, su MathWorld, Wolfram Research.
- (EN) The Great Internet Mersenne Prime Search, su mersenne.org.
- (EN) Storia su The Prime Pages
- (EN) Successione A000668 in OEIS
- Known Mersenne Primes (Numero primo più grande), su isthe.com. URL consultato il 18 ottobre 2018.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/af/Crystal128-kmplot.svg/25px-Crystal128-kmplot.svg.png)