Movatterモバイル変換

[0]ホーム
URL:

Vai al contenuto
WikipediaL'enciclopedia libera
Ricerca

Numero primo di Mersenne

Da Wikipedia, l'enciclopedia libera.

Inmatematica unnumero primo di Mersenne è unnumero primo inferiore di uno rispetto ad unapotenza di due. I numeri primi di Mersenne sono esprimibili come:

Mp=2p−1,{\displaystyle M_{p}=2^{p}-1,}

conp{\displaystyle p}intero positivoprimo; infatti, si può dimostrare che sen{\displaystyle n} non è primo, allora2n−1{\displaystyle 2^{n}-1} non è primo. Tale numerop{\displaystyle p} è talvolta indicato comeesponente di Mersenne (successioneA000043 inOEIS). Si noti che211−1=2047=23⋅89{\displaystyle 2^{11}-1=2047=23\cdot 89} non è primo e che quindi non tutti i numeri primi (nemmeno tutti quelli esprimibili nella forma2p−1{\displaystyle 2^{p}-1}) corrispondono a un esponente di Mersenne.

A volte nella definizione di numero primo di MersenneMn{\displaystyle M_{n}} non viene richiesto a priori che l'indicen{\displaystyle n} sia primo. L'equivalenza delle due definizioni segue dal fatto che seMn{\displaystyle M_{n}} è primo, allora anchen{\displaystyle n} deve essere primo, come si vede facilmente dall'identità

2ab−1=(2a−1)⋅(1+2a+22a+23a+⋯+2(b−1)a).{\displaystyle 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 tipoMn=2n−1{\displaystyle 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 degliMp{\displaystyle M_{p}} composti conp{\displaystyle p} primo. Ad esempio (eFermat fu il primo ad evidenziare e usare questa proprietà) si può dimostrare che ogni fattore primo diMp{\displaystyle M_{p}} dev'essere del tipo2kp+1{\displaystyle 2kp+1} conk{\displaystyle k} intero positivo[1].

I numeri primi di Mersenne prendono il nome dalmatematicofranceseMarin Mersenne (1588-1648). Mersenne compilò una lista di numeri primi di questo tipo considerando tutti i valori din{\displaystyle n} fino an=257{\displaystyle n=257}. Tale lista conteneva però alcuni errori: includevaM67{\displaystyle M_{67}} eM257{\displaystyle M_{257}} (che non sono primi), mentre non comparivanoM61{\displaystyle M_{61}},M89{\displaystyle M_{89}} eM107{\displaystyle M_{107}} (che sono primi).

I primi dodici numeri primi di Mersenne sono:

M2=22−1=3{\displaystyle M_{2}=2^{2}-1=3}
M3=23−1=7{\displaystyle M_{3}=2^{3}-1=7}
M5=25−1=31{\displaystyle M_{5}=2^{5}-1=31}
M7=27−1=127{\displaystyle M_{7}=2^{7}-1=127}
M13=213−1=8191{\displaystyle M_{13}=2^{13}-1=8191}
M17=131071{\displaystyle M_{17}=131071}
M19=524287{\displaystyle M_{19}=524287}
M31=2147483647{\displaystyle M_{31}=2147483647}
M61=2305843009213693951{\displaystyle M_{61}=2305843009213693951}
M89=618970019642690137449562111{\displaystyle M_{89}=618970019642690137449562111}
M107=162259276829213363391578010288127{\displaystyle M_{107}=162259276829213363391578010288127}
M127=170141183460469231731687303715884105727{\displaystyle M_{127}=170141183460469231731687303715884105727}

I numeri primi di Mersenne sono collegati con inumeri perfetti. Nel IV secolo a.C.Euclide dimostrò che seMn{\displaystyle M_{n}} è un numero primo, alloraMn⋅(Mn+1)2=2n−1⋅(2n−1){\displaystyle {M_{n}\cdot (M_{n}+1) \over 2}=2^{n-1}\cdot (2^{n}-1)} è unnumero perfetto.

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

L'avvento deicalcolatori elettronici ha notevolmente accelerato la scoperta dei primi di Mersenne. I primi dodici numeri primi di Mersenne sono stati scoperti prima delXX secolo. Alla fine del millennio i primi di Mersenne conosciuti erano 38; oggi sono noti almeno 52 numeri primi di Mersenne e i diciassette più recenti sono stati scoperti nell'ambito dellaGIMPS, laGreat 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 dalGIMPS è ilTest 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 22 novembre 2025) èM136279841{\displaystyle M_{136279841}}. Ha più di 41 milioni di cifre decimali ed è stato anch'esso trovato nell'ambito GIMPS:

M136279841=2136279841−1{\displaystyle M_{136279841}=2^{136279841}-1}[2]

Se scritti inbase 2, tutti i numeri primi di Mersenne sonorepunit 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 Mersenne2p−1{\displaystyle 2^{p}-1} , deve esserep{\displaystyle p} numero primo, questo deve essere dispari tranne nel caso dip=2{\displaystyle p=2} corrispondente all'unico numero di Mersenne terminante con 3 (il numero 3 appunto).

I primi di Mersenne, scritti in base 2, sono ancheprimi palindromi,primi permutabili eprimi di Gauss.

Lista numeri primi di Mersenne

[modifica |modifica wikitesto]
#pMpCifre inMpData scopertaScopritore
1231AntichitàIgnoto
2371AntichitàIgnoto
35312AntichitàIgnoto
471273AntichitàIgnoto
513819141456Ignoto
61713107161588Cataldi
71952428761588Cataldi
8312147483647101772Eulero
9612305843009213693951191883Pervušin
1089618970019642690137449562111271911Powers
11107162259276829213363391578010288127331914Powers
12127170141183460469231731687303715884105727391876Lucas
13521686479766…11505715115730 gennaio1952Robinson
14607531137992…03172812718330 gennaio1952Robinson
151.279104079321…16872908738625 giugno1952Robinson
162.203147597991…6977710076647 ottobre1952Robinson
172.281446087557…1328363516879 ottobre1952Robinson
183.217259117086…9093150719698 settembre1957Riesel
194.253190797007…35048499112813 novembre1961Hurwitz
204.423285542542…6085806071.3323 novembre1961Hurwitz
219.689478220278…2257541112.91711 maggio1963Gillies
229.941346088282…7894635512.99316 maggio1963Gillies
2311.213281411201…6963921913.3762 giugno1963Gillies
2419.937431542479…9680414716.0024 marzo1971Tuckerman
2521.701448679166…5118827516.53330 ottobre1978Noll eNickel
2623.209402874115…7792645116.9879 febbraio1979Noll
2744.497854509824…01122867113.3958 aprile1979Nelson eSlowinski
2886.243536927995…43343820725.96225 settembre1982Slowinski
29110.503521928313…46551500733.26528 gennaio1988Colquitt eWelsh
30132.049512740276…73006131139.75120 settembre1983Slowinski
31216.091746093103…81552844765.0506 settembre1985Slowinski
32756.839174135906…544677887227.83219 febbraio1992Slowinski eGage inHarwell LabCray-2
33859.433129498125…500142591258 71610 gennaio1994Slowinski eGage
341.257.787412245773…089366527378.6323 settembre1996Slowinski eGage
351.398.269814717564…451315711420.92113 novembre1996GIMPS / Joel Armengaud (PC Pentium 90)
362.976.221623340076…729201151895.93224 agosto1997GIMPS / Gordon Spence (PC Pentium 100)
373.021.377127411683…024694271909.52627 gennaio1998GIMPS / Roland Clarkson (Pentium 200)
386.972.593437075744…9241937912.098.9601º giugno1999GIMPS / Nayan Hajratwala (Pentium II 350)
3913.466.917924947738…2562590714.053.94614 novembre2001GIMPS / Michael Cameron (800 MHz AMD T-Bird PC)
4020.996.011125976895…8556820476.320.43017 novembre2003GIMPS / Michael Shafer (2 GHz Pentium 4 Dell Dimension PC)
4124.036.583299410429…7339694077.235.73315 maggio2004GIMPS / Josh Findley (2.4 GHz Pentium 4 Windows XP PC)
4225.964.951122164630…5770772477.816.23018 febbraio2005GIMPS / Martin Nowak (2.4 GHz Pentium 4 Windows XP PC)
4330.402.457315416475…6529438719.152.05215 dicembre2005GIMPS /Curtis Cooper eSteven Boone
4432.582.657124575026…0539678719.808.3584 settembre2006GIMPS /Curtis Cooper eSteven Boone
4537.156.667202254406…30822092711.185.2726 settembre2008GIMPS / Hans-Michael Elvenich, George Woltman, Scott Kurowski et al
4642.643.801169873516…56231475112.837.06412 aprile2009GIMPS / Odd M. Strindmo
4743.112.609316470269…69715251112.978.18923 agosto2008GIMPS / Edson Smith, George Woltman, Scott Kurowski et al
4857.885.161581887266…72428595117.425.17025 gennaio2013GIMPS / Curtis Cooper, George Woltman, Scott Kurowski et al
4974.207.281300376418084…39108643635122.338.6187 gennaio2016GIMPS / Curtis Cooper
5077.232.917467333183359…06976217907123.249.42526 dicembre2017GIMPS / Jonathan Pace
51?[3]82.589.933148894445742…32521790259124.862.0487 dicembre2018GIMPS / Patrick Laroche
52?136.279.841881694…87155141.024.32012 ottobre2024GIMPS / Luke Durant

Note

[modifica |modifica wikitesto]
  1. ^Mauro Fiorentini - Mersenne (numeri di), subitman.name.
  2. ^GIMPS Milestones Report, sumersenne.org.URL consultato il 21 dicembre 2018.
  3. ^Non è noto se esistano altri numeri primi di Mersenne tra il 50° (M77232917) e il 52° (M136279841) 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, sumersenne.org.URL consultato il 22 novembre 2025.

Voci correlate

[modifica |modifica wikitesto]

Altri progetti

[modifica |modifica wikitesto]

Collegamenti esterni

[modifica |modifica wikitesto]
  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica
Estratto da "https://it.wikipedia.org/w/index.php?title=Numero_primo_di_Mersenne&oldid=148130627"
Categoria:
Categorie nascoste:
[8]ページ先頭
©2009-2025 Movatter.jp