Hoppa till innehållet

Mersenneprimtal

Lägg till länkar
Från Plutten

Ett Mersenneprimtal är ett Mersennetal som är ett primtal, alltså ett primtal på formen 2n - 1.

Om Mersenneprimtal

[redigera | redigera wikitext]

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 upptäcktes den 12 oktober 2024 av Luke Durant. Det är 2136 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, (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: Ett nödvändigt men ej tillräckligt villkor för att ett Mersennetal ska 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 23 - 1, 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 tal) 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.

Denna tabell, gällande Mersennetal med exponenter upp till 100 000, visar att 9 592 av dessa Mersennetal har en primtalsexponent, men endast 28 av dem är Mersenneprimtal.[2][3]

Beskrivning (av talen i fet
stil med grön bakgrund) 		Antal tal då exponenten n ...
≤ 100 ≤ 1 000 ≤ 10 000 ≤ 100 000
Mersennetal 101 1 001 10 001 100 001
Har primtalsexponent 76 25 833 168 8 772 1 229 90 409 9 592
Är Mersenneprimtal 15 10 154 14 1 207 22 9 564 28

Denna tabell visar de 25 första Mersennetalen som har en primtalsexponent där Mersennetalen är sammansatta tal.[4][5][6]

Nr <math>p</math> <math>M_{p} = 2^p-1</math>
Värde Primtalsfaktorisering
1 11 2 047 23  ×  89
2 23 8 388 607 47  ×  178 481
3 29 536 870 911 233  ×  1 103  ×  2 089
4 37 137 438 953 471 223  ×  616 318 177
5 41 2 199 023 255 551 13 367  ×  164 511 353
6 43 8 796 093 022 207 431  ×  9 719  ×  2 099 863
7 47 140 737 488 355 327 2 351  ×  4 513  ×  13 264 529
8 53 9 007 199 254 740 991 6 361  ×  69 431  ×  20 394 401
9 59 576 460 752 303 423 487 179 951  ×  3 203 431 780 337
10 67 147 573 952 589 676 412 927 193 707 721  ×  761 838 257 287
11 71 2 361 183 241 434 822 606 847 228 479  ×  48 544 121  ×  212 885 833
12 73 9 444 732 965 739 290 427 391 439  ×  2 298 041  ×  9 361 973 132 609
13 79 604 462 909 807 314 587 353 087 2 687  ×  202 029 703  ×  1 113 491 139 767
14 83 9 671 406 556 917 033 397 649 407 167  ×  57 912 614 113 275 649 087 721
15 97 158 456 325 028 528 675 187 087 900 671 11 447  ×  13 842 607 235 828 485 645 766 393
16 101 2 535 301 200 456 458 802 993 406 410 751 7 432 339 208 719  ×  341 117 531 003 194 129
17 103 10 141 204 801 825 835 211 973 625 643 007 2 550 183 799  ×  3 976 656 429 941 438 590 393
18 109 649 037 107 316 853 453 566 312 041 152 511 745 988 807  ×  870 035 986 098 720 987 332 873
19 113 10 384 593 717 069 655 257 060 992 658 440 191 3 391  ×  23 279  ×  65 993  ×  1 868 569  ×  1 066 818 132 868 207
20 131 2 722 258 935 367 507 707 706 996 859 454 145 691 647 263  ×  10 350 794 431 055 162 386 718 619 237 468 234 569
21 137 174 224 571 863 520 493 293 247 799 005 065 324 265 471 32 032 215 596 496 435 569  ×  5 439 042 183 600 204 290 159
22 139 696 898 287 454 081 973 172 991 196 020 261 297 061 887 5 625 767 248 687  ×  123 876 132 205 208 335 762 278 423 601
23 149 713 623 846 352 979 940 529 142 984 724 747 568 191 373 311 86 656 268 566 282 183 151  ×  8 235 109 336 690 846 723 986 161
24 151 2 854 495 385 411 919 762 116 571 938 898 990 272 765 493 247 18 121  ×  55 871  ×  165 799  ×  2 332 951  ×  7 289 088 383 388 253 664 437 433
25 157 182 687 704 666 362 864 775 460 604 089 535 377 456 991 567 871 852 133 201  ×  60 726 444 167  ×  1 654 058 017 289  ×  2 134 387 368 610 417

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 tal), och man visste inte om det existerade några fler primtal i denna familj.

Lista över Mersenneprimtal

[redigera | redigera wikitext]
Nr p Mp = 2p - 1 Antal siffror i Mp 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 [7]
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 [8]
41 24 036 583 299410429…733969407 7 235 733 15 maj 2004 GIMPS / Josh Findley [9]
42 25 964 951 122164630…577077247 7 816 230 18 februari 2005 GIMPS / Martin Nowak [10]
43 30 402 457 315416475…652943871 9 152 052 15 december 2005 GIMPS / Curtis Cooper & Steven Boone [11]
44 32 582 657 124575026…053967871 9 808 358 4 september 2006 GIMPS / Curtis Cooper & Steven Boone [12]
45 37 156 667 202254406…308220927 11 185 272 6 september 2008 GIMPS / Hans-Michael Elvenich [13]
46 42 643 801 169873516…562314751 12 837 064 12 april 2009 GIMPS / Odd Magnar Strindmo [14]
47 43 112 609 316470269…697152511 12 978 189 23 augusti 2008 GIMPS / Edson Smith [13]
48 57 885 161 581887266…724285951 17 425 170 25 januari 2013 GIMPS / Curtis Cooper [15]
49 74 207 281 300376418…086436351 22 338 618 7 januari 2016 GIMPS / Curtis Cooper [16]
50 77 232 917 467333183…762179071 23 249 425 26 december 2017 GIMPS / Jonathan Pace [17]
51* 82 589 933 148894445...217902591 24 862 048 7 december 2018 GIMPS / Patrick Laroche [18]
52* 136 279 841 881694327...486871551 41 024 320 21 oktober 2024 GIMPS / Luke Durant [19]

*Mall:Sup Det är inte känt om det finns några oupptäckta Mersenneprimtal mellan det 50:e (M77 232 917) och det 52:a (M136 279 841) i den här tabellen. Därför kan ordningsnumren 51–52 komma att ändras.[20]

Se även

[redigera | redigera wikitext]

Referenser

[redigera | redigera wikitext]
  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. Läst 29 oktober 2024. 
  2. ↑ Antal primtal ≤ ett visst tal Mall:OEIS (längre/utförligare) (engelska)
  3. ↑ Exponenter i Mersenneprimtal Mall:OEIS (längre/utförligare) (engelska)
  4. ↑ Exponenter för Mersennetal med primtalsexponent som är sammansatta tal Mall:OEIS (längre/utförligare) (engelska)
  5. ↑ Mersennetal med primtalsexponent som är sammansatta tal Mall:OEIS (längre/utförligare) (engelska)
  6. ↑ Primtalsfaktorer för Mersennetal med primtalsexponent som är sammansatta tal Mall:OEIS (längre/utförligare) (engelska)
  7. ↑ Tal 32 (engelska)
  8. ↑ Tal 40 (engelska)
  9. ↑ Tal 41 (engelska)
  10. ↑ Tal 42 (engelska)
  11. ↑ Tal 43 (engelska)
  12. ↑ Tal 44 (engelska)
  13. ↑ 13,0 13,1 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.
  14. ↑ Tal 46, Tal 46 (engelska)
  15. ↑ Tal 48 (engelska)
  16. ↑ Tal 49 Arkiverad 7 januari 2018 hämtat från the Wayback Machine. (engelska)
  17. ↑ Tal 50 (engelska)
  18. ↑ Tal 51* (engelska)
  19. ↑ Tal 52* (engelska)
  20. ↑ ”Great Internet Mersenne Prime Search: Milestones Report” (på engelska). https://www.mersenne.org/report_milestones. Läst 8 september 2025. 

Externa länkar

[redigera | redigera wikitext]

Mall:Primtal Mall:Naturliga tal

Hämtad från ”https://wiki.viberq.org/w/index.php?title=Mersenneprimtal&oldid=33402”