Mersenneprimtal
Ett Mersennetal är inom talteorin ett heltal på formen 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
[redigera | redigera wikitext]I det binära talsystemet skrivs tal på formen som stycken ettor.
Om Mersenneprimtal
[redigera | redigera wikitext]Det är okänt huruvida det existerar ett oändligt antal Mersenneprimtal. Hittills har 51 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 är 282 589 933-1. Det upptäcktes den 7 december 2018 av Great Internet Mersenne Prime Search (GIMPS) och har 24 862 048 siffror.
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, (24 - 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 22j - 1 = (2j + 1)(2j - 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 211 - 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 27 - 1, 231 - 1 och 2127 - 1. Eftersom 213 - 1 (8 191) är ett primtal borde enligt denna förmodan också 28191 - 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
[redigera | redigera wikitext]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
- L0 = 4,
- Li+1 = Li2 - 2 mod 2p - 1.
För ett primtal p > 2 är 2p - 1 ett primtal om och endast om Lp-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 2127 - 1 (39-siffrigt), och man visste inte om det existerade några fler primtal i denna familj.
Lista över mersenneprimtal
[redigera | redigera wikitext]Nr | n | Mn | Antal siffror i Mn | 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 [1] |
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 [2] |
41 | 24 036 583 | 299410429…733969407 | 7 235 733 | 15 maj 2004 | GIMPS / Josh Findley [3] |
42 | 25 964 951 | 122164630…577077247 | 7 816 230 | 18 februari 2005 | GIMPS / Martin Nowak [4] |
43 | 30 402 457 | 315416475…652943871 | 9 152 052 | 15 december 2005 | GIMPS / Curtis Cooper & Steven Boone [5] |
44 | 32 582 657 | 124575026…053967871 | 9 808 358 | 4 september 2006 | GIMPS / Curtis Cooper & Steven Boone [6] |
45 | 37 156 667 | 202254406…308220927 | 11 185 272 | 6 september 2008 | GIMPS / Hans-Michael Elvenich [7] |
46 | 42 643 801 | 169873516…562314751 | 12 837 064 | 12 april 2009 | GIMPS / Odd Magnar Strindmo [8] |
47 | 43 112 609 | 316470269…697152511 | 12 978 189 | 23 augusti 2008 | GIMPS / Edson Smith [7] |
48 | 57 885 161 | 581887266…724285951 | 17 425 170 | 25 januari 2013 | GIMPS / Curtis Cooper [9] |
49* | 74 207 281 | 300376418…086436351 | 22 338 618 | 7 januari 2016 | GIMPS / Curtis Cooper [10] |
50* | 77 232 917 | 467333183…762179071 | 23 249 425 | 26 december 2017 | GIMPS / Jonathan Pace [11] |
51* | 82 589 933 | 148894445...217902591 | 24 862 048 | 7 december 2018 | GIMPS / Patrick Laroche [12] |
*) Det är inte känt om det finns några oupptäckta Mersenneprimtal mellan det 48:e (M 57 885 161 ) och det 51:a (M82 589 933) i den här tabellen, så därför finns risk att ordningsnumren på de sista talen inte stämmer.
Se även
[redigera | redigera wikitext]Referenser
[redigera | redigera wikitext]- ^ 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/kallades tal 46 vid upptäckten.
- ^ 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)
Externa länkar
[redigera | redigera wikitext]Wikimedia Commons har media som rör Mersenneprimtal.
- ”Mersenne Primes: History, Theorems and Lists” (på engelska). The University of Tennessee at Martin. http://primes.utm.edu/mersenne/index.html.
|
|