Mersenneprimtal

Ett Mersennetal $M_{n}$ är inom talteorin ett heltal på formen $2^{n}-1$ där n är ett positivt heltal. Det är uppkallat efter den franske amatörmatematikern Marin Mersenne (1588–1648).

Ett Mersenneprimtal är ett Mersennetal som är ett primtal.

Om Mersennetal

I det binära talsystemet skrivs tal på formen $2^{n}-1$ som $n$ stycken ettor.

Om Mersenneprimtal

Det är okänt huruvida det existerar ett oändligt antal Mersenneprimtal. Hittills har över 50 Mersenneprimtal hittats. De största av dessa är också de största kända primtalen, med flera miljoner siffror. Anledningen till att så stora Mersenneprimtal kunnat bestämmas är att det finns en särskilt effektiv algoritm för att avgöra om tal på den här formen är prima, nämligen Lucas-Lehmers test. Det största kända Mersenneprimtalet, fram till början av oktober 2024, är 2^{82 589 933}-1. Detta tal upptäcktes den 7 december 2018 av Great Internet Mersenne Prime Search (GIMPS) och har 24 862 048 siffror. Ett ännu större Mersenneprimtal upptäcktes den 12 oktober 2024 av Luke Durant. Det är 2^{136 279 841} -1, ett tal som innehåller 41 024 320 siffror.^[1]

De största kända primtalen är av Mersennetyp, men det är mycket sällsynt att Mersennetal är primtal. Till exempel så ger exponenten 4 talet 15, (2⁴ - 1 = 15), som är ett sammansatt tal. Detta förhållande gäller för samtliga jämna exponenter större än 2, eftersom exponenten då kan skrivas som 2j och Mersennetalet faktoruppdelas enligt modellen 2^2j - 1 = (2^j + 1)(2^j - 1).

Resultatet kan generaliseras: Mersennetalet är ett primtal endast om exponenten är ett primtal. Ett nödvändigt men ej tillräckligt villkor för att ett Mersennetal skall vara ett primtal är, att exponenten är ett primtal. Exempelvis är 2¹¹ - 1 = 2 047 inget primtal, ty 2 047 = 23·89.

Länge fanns en hypotes om att Mersennetal med Mersenneprimtal som exponent var primtal, vilket stämmer för 2⁷ - 1, 2³¹ - 1 och 2¹²⁷ - 1. Eftersom 2¹³ - 1 (8 191) är ett primtal borde enligt denna förmodan också 2⁸¹⁹¹ - 1 (2 466-siffrigt) vara det. Detta antagande visade sig vara falskt när man kunde undersöka talet med dator.

Flera liknande primtalshypoteser har sett dagens ljus, men samtliga har kunnat förpassas till papperskorgen. Det finns således ingen allmän tumregel eller "formel", med vilken man kan vaska fram Mersenneprimtal.

Sökning efter Mersenneprimtal

Det är relativt lätt att avgöra om ett Mersennetal är ett primtal eller inte.

Bortsett från några specialfall (de tal som slutar på 0, 5 eller är jämna, liksom de vars siffersumma är jämnt delbar med 3, kan till exempel inte vara primtal) finns inga "enkla" sätt att avgöra om ett godtyckligt tal är ett primtal. Även om det i det allmänna fallet finns bättre metoder än att tillgripa testdivision med samtliga primtal upp till kvadratroten ur talet, så krävs ofta ett enormt räknearbete för att kontrollera primtalsegenskapen.

För Mersennetal finns dock en enklare metod. På dessa kan man applicera det kriterium, som den franske matematikern Édouard Lucas uppställde i slutet av 1800-talet:

Bilda talföljden

L₀ = 4,

L_i+1 = L_i² - 2 mod 2^p - 1.

För ett primtal p > 2 är 2^p - 1 ett primtal om och endast om L_p-2 = 0, det vill säga om Mersennetalet går jämnt upp i termen med ordningsnumret p-2.

Också denna metod kräver ett mycket stort räknearbete för Mersennetal som består av tiotusentals (och ännu fler) siffror, men i motsats till de algoritmer som måste användas i det allmänna fallet för att avgöra om ett tal är primtal eller inte är den praktiskt utförbar.

Före datoråldern (med andra ord fram till början av 50-talet) kände man till 12 Mersenneprimtal, av vilka det största var 2¹²⁷ - 1 (39-siffrigt), och man visste inte om det existerade några fler primtal i denna familj.

Lista över Mersenneprimtal

Nr	n	M_n	Antal siffror i M_n	Upptäcktsdatum	Upptäckare
1	2	3	1	Forntida	Forntida
2	3	7	1	Forntida	Forntida
3	5	31	2	Forntida	Forntida
4	7	127	3	Forntida	Forntida
5	13	8191	4	1456	Anonym
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	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 januari 1952	Robinson
14	607	531137992…031728127	183	30 januari 1952	Robinson
15	1 279	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	1 281	3 november 1961	Hurwitz
20	4 423	285542542…608580607	1 332	3 november 1961	Hurwitz
21	9 689	478220278…225754111	2 917	11 maj 1963	Gillies
22	9 941	346088282…789463551	2 993	16 maj 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 & Nickel
26	23 209	402874115…779264511	6 987	9 februari 1979	Noll
27	44 497	854509824…011228671	13 395	8 april 1979	Nelson & Slowinski
28	86 243	536927995…433438207	25 962	25 september 1982	Slowinski
29	110 503	521928313…465515007	33 265	28 januari 1988	Colquitt & Welsh
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 februari 1992	Slowinski & Gage on Harwell Lab Cray-2 ^[2]
33	859 433	129498125…500142591	258 716	10 januari 1994	Slowinski & Gage
34	1 257 787	412245773…089366527	378 632	3 september 1996	Slowinski & Gage
35	1 398 269	814717564…451315711	420 921	13 november 1996	GIMPS / Joel Armengaud
36	2 976 221	623340076…729201151	895 932	24 augusti 1997	GIMPS / Gordon Spence
37	3 021 377	127411683…024694271	909 526	27 januari 1998	GIMPS / Roland Clarkson
38	6 972 593	437075744…924193791	2 098 960	1 juni 1999	GIMPS / Nayan Hajratwala
39	13 466 917	924947738…256259071	4 053 946	14 november 2001	GIMPS / Michael Cameron
40	20 996 011	125976895…855682047	6 320 430	17 november 2003	GIMPS / Michael Shafer ^[3]
41	24 036 583	299410429…733969407	7 235 733	15 maj 2004	GIMPS / Josh Findley ^[4]
42	25 964 951	122164630…577077247	7 816 230	18 februari 2005	GIMPS / Martin Nowak ^[5]
43	30 402 457	315416475…652943871	9 152 052	15 december 2005	GIMPS / Curtis Cooper & Steven Boone ^[6]
44	32 582 657	124575026…053967871	9 808 358	4 september 2006	GIMPS / Curtis Cooper & Steven Boone ^[7]
45	37 156 667	202254406…308220927	11 185 272	6 september 2008	GIMPS / Hans-Michael Elvenich ^[8]
46	42 643 801	169873516…562314751	12 837 064	12 april 2009	GIMPS / Odd Magnar Strindmo ^[9]
47	43 112 609	316470269…697152511	12 978 189	23 augusti 2008	GIMPS / Edson Smith ^[8]
48	57 885 161	581887266…724285951	17 425 170	25 januari 2013	GIMPS / Curtis Cooper ^[10]
49*	74 207 281	300376418…086436351	22 338 618	7 januari 2016	GIMPS / Curtis Cooper ^[11]
50*	77 232 917	467333183…762179071	23 249 425	26 december 2017	GIMPS / Jonathan Pace ^[12]
51*	82 589 933	148894445...217902591	24 862 048	7 december 2018	GIMPS / Patrick Laroche ^[13]
52*	136 279 841	881694327...486871551	41 024 320	21 oktober 2024	GIMPS / Luke Durant ^[14]

*⁾ Det är inte känt om det finns några oupptäckta Mersenneprimtal mellan det 48:e (M_{57 885 161}) och det 52:a (M_{136 279 841}) i den här tabellen. Därför kanske ordningsnumren 49–52 inte stämmer.

Se även

Great Internet Mersenne Prime Search

Referenser

^ Bill Burrau (26 oktober 2024). ”Nytt världsrekord för primtal – hittades med hjälp av grafikprocessorer”. www.nyteknik.se. https://www.nyteknik.se/tech/nytt-varldsrekord-for-primtal-hittades-med-hjalp-av-grafikprocessorer/4300312?utm_source=rule&utm_medium=email&utm_campaign=bilarna%20har%20samma%20teknik%20%E2%80%93%20den%20ena%20krockar,%20den%20andra%20klarar%20sig&utm_custom%5Brm%5D=312258798. Läst 29 oktober 2024.
^ Tal 32 (engelska)
^ Tal 40 (engelska)
^ Tal 41 (engelska)
^ Tal 42 (engelska)
^ Tal 43 (engelska)
^ Tal 44 (engelska)
^ [a b] Tal 45 och 47 (engelska) Tal 47 var först tal 45 vid upptäckten och därefter tal 46 innan det fastställdes som tal 47.
^ Tal 46, Tal 46 (engelska)
^ Tal 48 (engelska)
^ Tal 49* Arkiverad 7 januari 2018 hämtat från the Wayback Machine. (engelska)
^ Tal 50* (engelska)
^ Tal 51* (engelska)
^ Tal 52* (engelska)

Externa länkar

Wikimedia Commons har media som rör Mersenneprimtal.
Bilder & media
”Mersenne Primes: History, Theorems and Lists” (på engelska). The University of Tennessee at Martin. http://primes.utm.edu/mersenne/index.html.

[1] Bill Burrau (26 oktober 2024). ”Nytt världsrekord för primtal – hittades med hjälp av grafikprocessorer”. www.nyteknik.se. https://www.nyteknik.se/tech/nytt-varldsrekord-for-primtal-hittades-med-hjalp-av-grafikprocessorer/4300312?utm_source=rule&utm_medium=email&utm_campaign=bilarna%20har%20samma%20teknik%20%E2%80%93%20den%20ena%20krockar,%20den%20andra%20klarar%20sig&utm_custom%5Brm%5D=312258798. Läst 29 oktober 2024.

[2] Tal 32 (engelska)

[3] Tal 40 (engelska)

[4] Tal 41 (engelska)

[5] Tal 42 (engelska)

[6] Tal 43 (engelska)

[7] Tal 44 (engelska)

[A-8] [a b] Tal 45 och 47 (engelska) Tal 47 var först tal 45 vid upptäckten och därefter tal 46 innan det fastställdes som tal 47.

[9] Tal 46, Tal 46 (engelska)

[10] Tal 48 (engelska)

[11] Tal 49* Arkiverad 7 januari 2018 hämtat från the Wayback Machine. (engelska)

[12] Tal 50* (engelska)

[13] Tal 51* (engelska)

[14] Tal 52* (engelska)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]