Hlavní navigace

Mersennovo prvočíslo nalezeno?

Pavel Vondruška 16. 11. 2001

Dosud největší známé prvočíslo má více jak milión cifer (přesně 2 098 960). Zdá se, že rekord, který toto číslo drží od roku 1999, bude v nejbližší době překonán! Na Slashdotu bylo 14. 11. 2001 jedním z čtenářů oznámeno, že bylo pravděpodobně nalezeno 39. (třicáté deváté) Mersennovo prvočíslo.

Na adrese ftp://entropi­a.com/gimps/pri­me4.txt je dostupné dosud největší známé prvočíslo 26 972 593-1. Toto prvočíslo je prvé známé megaprvočíslo, tedy prvočíslo, které má více jak milión cifer (přesně 2 098 960!), druhé největší známé prvočíslo 23 021 377-1 (třicáté sedmé Mersennovo prvočíslo) má „jen“ 909 526 cifer. Pro lepší představu o jeho velikosti uvedeme, že při tisku (bold 10) zabere cca 110 stránek A4. Při zápisu do řady, kde jedna číslice je široká 1 mm a mezery mezi číslicemi zanedbáme, by bylo toto číslo více jak 2 km dlouhé.

Zdá se, že rekord, který toto číslo drží od roku 1999, bude v nejbližší době překonán! Na Slashdotu bylo 14. 11. 2001 jedním z čtenářů oznámeno, že bylo pravděpodobně nalezeno 39. (třicáté deváté) Mersennovo prvočíslo. Očekává se, že Primenet, který hledání tohoto čísla organizoval, tuto zprávu přibližně do týdne oficiálně potvrdí (24. 11. 2001). (http://www.ut­m.edu/research/pri­mes/mersenne.shtml)

Jaký bude nový rekordman? Toto číslo bude mít více jak 3 500 000 cifer, stane se tedy dosud největším známým prvočíslem. Jeho velikost je pro odborníky tak trochu překvapením. Matematici totiž předpokládali, že 39. Mersennovo prvočíslo bude ještě výrazně větší a odhadovali, že by mohlo mít až 10 000 000 cifer.

Co jsou vlastně Mersennova prvočísla?

Mersennova prvočísla jsou prvočísla speciálního tvaru, a to Mn = 2n – 1. Aby číslo uvedeného tvaru mohlo být prvočíslo, musí být exponent n prvočíslem. Jedná se ovšem jen o podmínku nutnou.

Začátkem 17. století vyslovil francouzský matematik (a teolog) Marin MERSENNE (1588 – 1648) hypotézu, že pro n menší jak 258 jsou čísla tvaru Mn = 2n  – 1 prvočísly právě pro n = 1, 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257

Prvočísla tvaru Mn = 2n – 1 se v současné době na jeho počest nazývají Mersennova prvočísla.

Mersennova prvočísla se zapisují vzestupně do tabulky a je zvykem je označovat pořadovým číslem v této tabulce. Tabulka dosud nalezených Mersennových prvočísel je uvedena jako příloha k tomuto článku.

Vraťme se k Mersennově hypotéze. Hypotéza byla v následujících letech testována mnoha matematiky a postupně se podařilo odstranit chyby, které obsahovala.

V intervalu 1–257 byla vynechána celkem tři Mersennova prvočísla a naopak dvě z uvedených čísel jsou čísla složená:

  • vynechána byla deváté, desáté a jedenácté Mersennovo prvočísla, tedy M61 , M89 a M107 (přičemž pro n=61, M61 =261 – 1 byla prvočíselnost dokázána teprve v roce 1883)
  • složenými čísly jsou naopak M67 a M257 (Číslo M67 = 267  – 1 = 193707721*761­838257287 rozložil Cole roku 1903)

Důležitým kritériem, zda Mersennovo číslo je, nebo není prvočíslo, je Lucas (1870)-Lehmerův (1930) test. Síla tohoto testu je mimo jiné v tom, že jej lze snadno zrealizovat pomocí výpočetní techniky.

Lucas-Lehmerův test:

Nechť n je liché prvočíslo. Pak je Mn prvočíslem právě tehdy, když dělí číslo S(n-2), kde S(0)=4, S(k+1) = S(k)2 – 2.

Podrobnosti (včetně vysvětlení použitého značení) naleznete např. na adrese http://www.ut­m.edu/research/pri­mes/notes/pro­ofs/LucasLehmer­.html

Koncem roku 1998 bylo nalezeno celkem 37 Mersennových prvočísel. Na základě rozboru všech těchto prvočísel byla vytvořena hypotéza o jejich rozložení a byly experimentálně určeny parametry lineární funkce, která určuje závislost exponentu n Mersennova čísla na jeho pořadí v tabulce (tzv „lineární hypotéza“). Z této „lineární hypotézy“ se dalo očekávat, že třicáté osmé Mersennovo prvočíslo bude mít exponent přibližně roven 4,699,385. Při systematickém prohledávání vhodných kandidátů bylo v roce 1999 objeveno nové Mersennovo prvočíslo (v současné době označováno jako třicáté osmé), jenže jeho exponent je 6972593, což by bylo v dobré shodě pro třicáté deváté Mersennovo prvočíslo (předpověď z lineární hypotézy je: 6,935,171). Řada odborníků se tedy domnívala, že při prohledávání prostoru kandidátů na třicáté osmé Mersennovo prvočíslo se podařilo příslušnou hodnotu „přeskočit“. Na projektu se podílely stovky dobrovolníků, kteří hypotézu testovali na svých PC, a je tedy možné, že některý z dobrovolníků „selhal“. V roce 2000 a 2001 byl tento prostor znovu prohledáván. V každém případě poslední objevené Mersennovo prvočíslo bylo až dosud největším známým prvočíslem a stalo se prvým megaprvočíslem  – tedy prvočíslem, které má ve svém dekadickém zápisu více jak milión cifer.

Příloha 1: „Lineární hypotéza“ rozložení Mersennových prvočísel

eG log2 n – 1.462 With Respect to N, and the Line y = x
(G je Eulerova gamma funkce (0.5772156649…) a e je základ přirozeného logaritmu (2.718281828…))

Očekávané hodnoty exponentu n pro n-té Mersennovo prvočíslo, vypočtené podle „lineární hypotézy“

N exponent n v 2n-1
38 4,699,385
39 6,935,171
40 10,234,658
41 15,103,913
42 22,289,772
43 32,894,385
44 48,544,264
45 71,639,751
50 501,458,270

Pokud se potvrdí zpráva na Sladshotu a bylo nalezeno 39. Mersennovo prvočíslo, jehož velikost bude skutečně „jen“ 3 500 000 cifer, bude zde argument pro to, že lineární hypotéza prostě neplatí! Tím by se také dalo vysvětlit, proč již při hledání 38. Mersennova prvočísla nebylo s jeho očekávanou délkou vše úplně v pořádku. Prostě by se jen potvrdilo, že o rozložení prvočísel toho zatím víme málo a jedná se stále o jeden z otevřených problémů, patřících mezi krásné nerozřešené záhady matematiky.

Příloha 2: Tabulka všech dosud nalezených Mersennových prvočísel

Tabulka č. 209
Pořadí N n Cifer Rok Objevil
1 1 1  – Starověké Řecko
2 3 1  – Starověké Řecko
3 5 2  – Starověké Řecko
4 7 3  – Starověké Řecko
5 13 4 1456 ?
6 17 6 1588 Cataldi
7 19 6 1588 Cataldi
8 31 10 1772 Euler
9 61 19 1883 Pervušin
10 89 27 1911 Powers
11 107 33 1914 Powers
12 127 39 1876 Lucas
13 521 157 1952 Robinson
14 607 183 1952 Robinson
15 1279 386 1952 Robinson
16 2203 664 1952 Robinson
17 2281 687 1952 Robinson
18 3217 969 1957 Riesel
19 4253 1281 1961 Hurwitz
20 4423 1332 1961 Hurwitz
21 9689 2917 1963 Gillies
22 9941 2993 1963 Gillies
23 11213 3376 1963 Gillies
24 19937 6002 1971 Tucker
25 21701 6533 1978 Noll,Nickel
26 23209 6987 1979 Noll
27 44497 13395 1979 Nelson, Slowinski
28 86243 25962 1982 Slowinski
29 110503 33256 1988 Colquitt, Welsh
30 132049 39751 1983 Slowinski
31 216091 65050 1985 Slowinski
32 756839 227832 1992 Slowinski, Gage
33 859433 258716 1994 Slowinski, Gage
34 1257787 378623 1996 Slowinski, Gage
35 1398269 420921 1996 GIMPS
36 2976221 895932 1997 GIMPS
37 3021377 909,526 1998 GIMPS
38* 6972593 2,098,960 1999 GIMPS
39** ? 3 500 000 2001 GIMPS

* 1.6. 1999, Nayan Hajratwala, GIMPS the Great Internet Mersenne Prime Search

** http://www.ut­m.edu/research/pri­mes/mersenne.shtml

------------------------------------------

Adresy pro zvídavé zájemce:

Mersennova prvočísla – přehled: http://homepa­ges.go.com/~jo­ekorovin/Mersen­ne.html
Uloženo celé 38 Mersennovo prvočíslo ftp://entropi­a.com/gimps/pri­me4.txt
Lucas-Lehmer test: http://www.ut­m.edu/research/pri­mes/notes/pro­ofs/LucasLehmer­.html
Caldwell, Chris K. „Mersenne Primes: History, Theorems and Lists.“ Prime Pages
(1999). Online. Internet. Accessed November 22, 1999. Available HTTP: http://www.ut­m.edu/research/pri­mes/mersenne.shtml Caldwell, Chris K. „The Largest Known Prime by Year: A Brief History.“ Prime Pages
(1999). Online. Internet. Accessed November 22, 1999. Available HTTP:
http://www.ut­m.edu/research/pri­mes/notes/by_y­ear.html
Caldwell, Chris K. „Where is the next larger Mersenne prime?“ Prime Pages (1999).
Online. Internet. Accessed November 22, 1999. Available HTTP:
http://www.ut­m.edu/research/pri­mes/notes/faq/Nex­tMersenne.html
Caldwell, Chris K. „Lucas-Lehmer Theorem.“ Prime Pages (1999). Online. Internet.
Accessed November 22, 1999. Available HTTP: http://www.ut­m.edu/research/pri­mes/notes/pro­ofs/LucasLehmer­.html
Caldwell, Chris K. „Modular restrictions on Mersenne divisors.“ Prime Pages (1999).
Online. Internet. Accessed November 22, 1999. Available HTTP: http://www.ut­m.edu/research/pri­mes/notes/pro­ofs/MerDiv.html
Caldwell, Chris K. „Prime-square Mersenne divisors are Wieferich.“ Prime Pages
(1999). Online. Internet.Accessed November 22, 1999. Available HTTP: http://www.ut­m.edu/research/pri­mes/notes/pro­ofs/SquareMer­Div.html
Kurowski, Scott. „Current Internet PrimeNet Server World Test Status.“ Entropia.com
(November 22, 1999). Online. Internet. Accessed November 22, 1999. Available HTTP: http://entropi­a.com/primenet
O’Connor, John J., and Robertson, Edmund F. „Prime numbers.“ The MacTutor History
of Mathematics Archive (December 1996). Online. Internet. Accessed
November 22, 1999. Available HTTP: http://www-history.mcs.st-andrews.ac.uk/his­tory/HistTopic­s/Prime_number­s.html
Williams, Hugh C. édouard Lucas and Primality Testing. New York: John Wiley & Sons, Inc., 1998.
Wiman, Lucas, et al. „The Mersenne Prime Mailing List FAQ.“ Mersenne FAQ (1999).
Online. Internet. Accessed November 22, 1999. Available HTTP: http://www.ta­sam.com/~lrwi­man/faq-mers
Woltman, George. „38th Mersenne Prime Discovered.“ Mersenne.org (June 30, 1999).
Online. Internet. Accessed November 22, 1999. Available HTTP: http://www.mer­senne.org/6972593­.htm
Woltman, George. „Mersenne Prime Search.“ Mersenne.org (October 4, 1999). Online.
Internet. Accessed November 22, 1999. Available HTTP: http://www.mer­senne.org/pri­me.htm

Našli jste v článku chybu?

15. 7. 2005 19:19

Matematik (neregistrovaný)
O tom se žádné akademické spory nevedou. Prvočíslem je takové přirozené číslo, které má PRÁVĚ DVA RŮZNÉ dělitele - jedničku a sebe samo. Jednička tudíž prvočíslem není.

Nula není přirozené číslo, nemůže být tedy prvočíslem.
Parita je opět vlastností přirozených čísel, ptát se, je-li nula lichá nebo sudá je stejný nesmysl, jako ptát se, jsou-li 2/3 sudé nebo liché číslo.
Nula nulou vydělit nejde, jelikož dělení nulou není definováno.
Zbylé dvě otázky nemají smysl (navíc s tím, že cokoliv děleno …




7. 3. 2004 22:35

dworkin (neregistrovaný)

6/2=3 => 6=3*2 = 2+2+2
10/5=2 => 10=2*5 = 5+5
0/0=? => 0=?*0 = 0 = 0+0 = 0+0+0 = 0+0+0+0...
=> ?=0,1,2,3,...




Lupa.cz: Kdo pochopí vtip, může jít do ČT vyvíjet weby

Kdo pochopí vtip, může jít do ČT vyvíjet weby

Lupa.cz: Proč firmy málo chrání data? Chovají se logicky

Proč firmy málo chrání data? Chovají se logicky

Podnikatel.cz: Přehledná titulka, průvodci, responzivita

Přehledná titulka, průvodci, responzivita

Lupa.cz: Teletext je „internetem hipsterů“

Teletext je „internetem hipsterů“

Vitalia.cz: 7 originálních adventních kalendářů pro mlsné

7 originálních adventních kalendářů pro mlsné

Vitalia.cz: Paštiky plné masa ho zatím neuživí

Paštiky plné masa ho zatím neuživí

Měšec.cz: Jak vymáhat výživné zadarmo?

Jak vymáhat výživné zadarmo?

DigiZone.cz: Flix TV má set-top box s HEVC

Flix TV má set-top box s HEVC

Měšec.cz: Jak levně odeslat balík přímo z domu?

Jak levně odeslat balík přímo z domu?

Podnikatel.cz: Zavře krám u #EET Malá pokladna a Teeta?

Zavře krám u #EET Malá pokladna a Teeta?

Vitalia.cz: Láska na vozíku: Přitažliví jsme pro tzv. pečovatelky

Láska na vozíku: Přitažliví jsme pro tzv. pečovatelky

Vitalia.cz: 9 největších mýtů o mase

9 největších mýtů o mase

Vitalia.cz: Dáte si jahody s plísní?

Dáte si jahody s plísní?

Podnikatel.cz: K EET. Štamgast už peníze na stole nenechá

K EET. Štamgast už peníze na stole nenechá

Podnikatel.cz: Udávání kvůli EET začalo

Udávání kvůli EET začalo

Lupa.cz: Propustili je z Avastu, už po nich sahá ESET

Propustili je z Avastu, už po nich sahá ESET

Vitalia.cz: Spor o mortadelu: podle Lidlu falšovaná nebyla

Spor o mortadelu: podle Lidlu falšovaná nebyla

DigiZone.cz: Recenze Westworld: zavraždit a...

Recenze Westworld: zavraždit a...

DigiZone.cz: ČT má dalšího zástupce v EBU

ČT má dalšího zástupce v EBU

Vitalia.cz: Říká amoleta - a myslí palačinka

Říká amoleta - a myslí palačinka