Numero primo di Mersenne

In matematica un numero primo di Mersenne è un numero primo inferiore di uno rispetto ad una potenza di due. È quindi 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à

2^{ab}-1=(2^{a}-1)\cdot \left(1+2^{a}+2^{2a}+2^{3a}+\cdots +2^{(b-1)a}\right).

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 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) è $M_{82589933}$ . Ha più di 24 milioni di cifre decimali ed è stato anch'esso trovato nell'ambito GIMPS:

M_{82589933}=2^{82589933}-1

^[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:

3₁₀ = 11₂

7₁₀ = 111₂

31₁₀ = 11111₂

127₁₀ = 1111111₂

8191₁₀ = 1111111111111₂.

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 $2^{p}-1$ , deve essere $p$ numero primo, questo deve essere dispari tranne nel caso di $p=2$ 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 modifica

#	p	M_p	Cifre in M_p	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 modifica

^ 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.