Primnummer til Mersenne

I matematikk er et Mersenne-primtall et primtall som er én lavere enn en potens av to . Det kan derfor uttrykkes som:

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

med et primtall positivt heltall . Dette tallet blir noen ganger referert til som Mersenne-eksponenten (suksesjon A000043 i OEIS ). Merk at det ikke er primtall, og derfor tilsvarer ikke alle primtall en Mersenne-eksponent, men bare de som det også er primtall for. $s$ $s$ ${\ displaystyle 2 ^ {11} -1 = 2047 = 23 \ cdot 89}$ ${\ displaystyle M_ {p} = 2 ^ {p} -1}$

Noen ganger i definisjonen av Mersenne-primtall kreves det ikke på forhånd at indeksen skal være primtall. Ekvivalensen mellom de to definisjonene følger av det faktum at hvis det er primtall, så må det også være primtall, som lett kan ses av identiteten $M_n$ $n$ ${\ displaystyle M_ {n}}$ $n$

{\ displaystyle 2 ^ {ab} -1 = (2 ^ {a} -1) \ cdot \ venstre (1 + 2 ^ {a} + 2 ^ {2a} + 2 ^ {3a} + \ cdots + 2 ^ {(b-1) a} \ høyre).}

Generelt kalles et slikt tall et "Mersenne-tall" (selv når det ikke er et Mersenne-primtall). Flere egenskaper til prime faktorer av prime forbindelser er kjent . For eksempel (og Fermat var den første som fremhevet og brukte denne egenskapen) kan det vises at hver primfaktor av må være av den positive heltallstypen [ 1] . ${\ displaystyle M_ {n} = 2 ^ {n} -1}$ $M_p$ $s$ $M_p$ ${\ displaystyle 2kp + 1}$ $k$

Mersennes primtall er oppkalt etter den franske matematikeren Marin Mersenne ( 1588 - 1648 ). Mersenne kompilerte en liste over primtall av denne typen med tanke på alle verdier på opptil . Denne listen inneholdt imidlertid noen feil: den inkluderte og (som ikke er prime), mens de ikke dukket opp , og (som er prime). $n$ ${\ displaystyle n = 257}$ ${\ displaystyle M_ {67}}$ ${\ displaystyle M_ {257}}$ ${\ displaystyle M_ {61}}$ ${\ displaystyle M_ {89}}$ ${\ displaystyle M_ {107}}$

De første tolv Mersenne-primtallene er:

{\ displaystyle M_ {2} = 2 ^ {2} -1 = 3}

{\ displaystyle M_ {3} = 2 ^ {3} -1 = 7}

{\ displaystyle M_ {5} = 2 ^ {5} -1 = 31}

{\ displaystyle M_ {7} = 2 ^ {7} -1 = 127}

{\ displaystyle M_ {13} = 2 ^ {13} -1 = 8191}

{\ displaystyle M_ {17} = 131071}

{\ displaystyle M_ {19} = 524287}

{\ displaystyle M_ {31} = 2147483647}

{\ displaystyle M_ {61} = 2305843009213693951}

{\ displaystyle M_ {89} = 618970019642690137449562111}

{\ displaystyle M_ {107} = 162259276829213363391578010288127}

{\ displaystyle M_ {127} = 170141183460469231731687303715884105727}

Mersenne-primtall er relatert til perfekte tall . På 400-tallet f.Kr. beviste Euklid at hvis det er et primtall, så er det et perfekt tall . $M_n$ ${\ displaystyle {M_ {n} \ cdot (M_ {n} +1) \ over 2} = 2 ^ {n-1} \ cdot (2 ^ {n} -1)}$

På 1700-tallet beviste Euler at alle jevne perfekte tall har denne formen. Ingen oddetall er kjent, og det er også mulig at ingen eksisterer.

Fremkomsten av elektroniske datamaskiner akselererte i stor grad oppdagelsen av den tidlige Mersenne. De første tolv Mersenne-primtallene ble oppdaget før det 20. århundre . På slutten av årtusenet var de tidligste kjente Mersenne 38; i dag er imidlertid 51 kjent og de siste sytten har blitt oppdaget innenfor GIMPS , Great Internet Mersenne Prime Search , et initiativ som utnytter de tilgjengelige ressursene til tusenvis av datamaskiner på nettverket for å søke etter den første av Mersenne. Primalitetstesten brukt av GIMPS er Lucas-Lehmer-testen som er mye raskere enn de generiske testene med samme størrelsesorden i antall; det er grunnen til at registreringene av de største kjente primtallene lenge har vært Mersenne-primtall. Det største kjente primtallet (per 21. desember 2018) er . Den har mer enn 24 millioner desimaler og ble også funnet i GIMPS-omfanget: ${\ displaystyle M_ {82589933}}$

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

[2]

Hvis skrevet i grunntall 2 , er alle Mersenne-primtall repunit-primtal , det vil si at de er representert av strenger av p - enhetssiffer, der p er Mersenne-primtallseksponenten. I eksemplene nedenfor angir indeksen basen som tallet er uttrykt i:

3 10 = 11 2 7 10 = 111 2 31 10 = 11 111 2 127 10 = 1111111 2 8191 10 = 1111111111111 2 .

Merk at denne egenskapen er i besittelse når 1 trekkes fra alle potenser av 2 med et primtall som eksponent. I utgangspunktet er alle kandidater til å være Mersenne-primtall (kalt ganske enkelt "Mersenne-tall" som nevnt ovenfor) i binær notasjon primtallsreenheter.

Det kan observeres ved å bla nedover listen nedenfor, at bortsett fra 3, ender alle Mersenne-primtall på 1 eller 7. Dette skyldes at potensene til 2 ender syklisk med 2, 4, 8, 6, når eksponenten er henholdsvis av formen 1 + 4k, 2 + 4k, 3 + 4k og 4 + 4k (k positivt naturlig tall). Av denne grunn har bare potensene til 2 som slutter på 2 og 8 eksponenter av formen 1 + 4k og 3 + 4k, det vil si at de har odde eksponenter, mens de som slutter på 4 og 6 har partallseksponenter. Til slutt, gitt at i et primtall av Mersenne , må det være primtall, dette må være oddetall, bortsett fra når det tilsvarer det eneste tallet av Mersenne som slutter med 3 (tallet 3 faktisk). $2 ^ {p} -1$ $s$ $p = 2$

Mersenne-primtall, skrevet i base 2, er også palindromiske primtall , permuterbare primtall og Gauss-primtall .

Mersenne primtallsliste

#	s	M p	Tall i M s	Oppdagelsesdato	Oppdager
1	2	3	1	Antikken	Ukjent
2	3	7	1	Antikken	Ukjent
3	5	31	2	Antikken	Ukjent
4	7	127	3	Antikken	Ukjent
5	1. 3	8191	4	1456	Ukjent
6	17	131071	6	1588	Cataldi
7	19	524287	6	1588	Cataldi
8	31	2147483647	10	1772	Euler
9	61	2305843009213693951	19	1883	Pervushin
10	89	618970019642690137449562111	27	1911	Krafter
11	107	1622592768292133633391578010288127	33	1914	Krafter
12	127	170141183460469231731687303715884105727	39	1876	Lucas
1. 3	521	686479766… 115057151	157	30. januar 1952	Robinson
14	607	531137992… 031728127	183	30. januar 1952	Robinson
15	1279	104079321… 168729087	386	25. juni 1952	Robinson
16	2.203	147597991… 697771007	664	7. oktober 1952	Robinson
17	2.281	446087557… 132836351	687	9. oktober 1952	Robinson
18	3.217	259117086… 909315071	969	8. september 1957	Riesel
19	4.253	190797007… 350484991	1281	3. november 1961	Hurwitz
20	4.423	285542542… 608580607	1.332	3. november 1961	Hurwitz
21	9.689	478220278… 225754111	2.917	11. mai 1963	Gillies
22	9,941	346088282… 789463551	2.993	16. mai 1963	Gillies
23	11.213	281411201… 696392191	3.376	2. juni 1963	Gillies
24	19.937	431542479… 968041471	6.002	4. mars 1971	Tuckerman
25	21.701	448679166… 511882751	6.533	30. oktober 1978	Noll og nikkel
26	23.209	402874115… 779264511	6.987	9. februar 1979	Noll
27	44.497	854509824… 011228671	13.395	8. april 1979	Nelson og Slowinski
28	86.243	536927995… 433438207	25.962	25. september 1982	Slowinski
29	110.503	521928313… 465515007	33.265	28. januar 1988	Colquitt og walisisk
30	132.049	512740276… 730061311	39.751	20. september 1983	Slowinski
31	216.091	746093103… 815528447	65.050	6. september 1985	Slowinski
32	756.839	174135906… 544677887	227.832	19. februar 1992	Slowinski og Gage i Harwell Lab Cray-2
33	859.433	129498125 ... 500142591	258 716	10. januar 1994	Slowinski og Gage
34	1 257 787	412245773… 089366527	378.632	3. september 1996	Slowinski og Gage
35	1 398 269	814717564… 451315711	420.921	13. november 1996	GIMPS / Joel Armengaud (PC Pentium 90)
36	2.976.221	623340076… 729201151	895.932	24. august 1997	GIMPS / Gordon Spence (PC Pentium 100)
37	3.021.377	127411683… 024694271	909.526	27. januar 1998	GIMPS / Roland Clarkson (Pentium 200)
38	6.972.593	437075744… 924193791	2 098 960	1. juni 1999	GIMPS / Nayan Hajratwala (Pentium II 350)
39	13.466.917	924947738 ... 256259071	4.053.946	14. november 2001	GIMPS / Michael Cameron (800 MHz AMD T-Bird PC)
40	20.996.011	125976895… 855682047	6.320.430	17. november 2003	GIMPS / Michael Shafer (2 GHz Pentium 4 Dell Dimension PC)
41	24.036.583	299410429… 733969407	7.235.733	15. mai 2004	GIMPS / Josh Findley (2,4 GHz Pentium 4 Windows XP PC)
42	25.964.951	122164630… 577077247	7.816.230	18. februar 2005	GIMPS / Martin Nowak (2,4 GHz Pentium 4 Windows XP PC)
43	30.402.457	315416475… 652943871	9.152.052	15. desember 2005	GIMPS / Curtis Cooper og Steven Boone
44	32.582.657	124575026… 053967871	9.808.358	4. september 2006	GIMPS / Curtis Cooper og Steven Boone
45	37.156.667	202254406… 308220927	11.185.272	6. september 2008	GIMPS / Hans-Michael Elvenich, George Woltman, Scott Kurowski et al
46	42.643.801	169873516… 562314751	12.837.064	12. april 2009	GIMPS / Odd M. Strindmo
47	43.112.609	316470269… 697152511	12.978.189	23. august 2008	GIMPS / Edson Smith, George Woltman, Scott Kurowski et al
48	57.885.161	581887266… 724285951	17.425.170	25. januar 2013	GIMPS / Curtis Cooper, George Woltman, Scott Kurowski et al
49? [3]	74.207.281	300376418084 ... 391086436351	22.338.618	7. januar 2016	GIMPS / Curtis Cooper
50? [3]	77.232.917	467333183359… 069762179071	23.249.425	26. desember 2017	GIMPS / Jonathan Pace
51? [3]	82.589.933	148894445742… 325217902591	24.862.048	7. desember 2018	GIMPS / Patrick Laroche

Merknader

^ Mauro Fiorentini - Mersenne (antall)
^ GIMPS Milestones Report , på mersenne.org . Hentet 21. desember 2018 .
^ a b c Det er ikke kjent om andre Mersenne-primtal eksisterer mellom den 48. (M57885161) og den 51. (M82589933), og nummereringen av tabellen er derfor foreløpig i den siste delen. Mersenne-primtal har ikke alltid blitt oppdaget i stigende rekkefølge. For eksempel ble Mersennes 29. primtall oppdaget etter 30. og 31. Tilsvarende ble den 47. fulgt av to andre mindre tall, en oppdaget to uker senere og den andre 8 måneder senere. GIMPS Milestones Report , på mersenne.org . Hentet 2. juni 2022 .

Relaterte elementer

Andre prosjekter

Wikinews inneholder artikkelen Two New Largest Prime Numbers Discovered Within Days , 18. september 2008

Eksterne lenker

( NO ) The Great Internet Mersenne Prime Search , på mersenne.org .
( NO ) Historie i The Prime Pages
( EN ) Etterfølge A000668 i OEIS
Kjente Mersenne Primes (Greatest Prime Number) , på isthe.com . Hentet 18. oktober 2018 .