P R E S E K
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652 Letnik 31 (2003/2004) Številka 6 Strani 345-346
Ciril Petr:
ODKRITO NOVO NAJVEČJE (MERSENNOVO) PRA-ŠTEVILO
Ključne besede: novice, teorija števil, računalništvo, praštevila, Mer-sennova števila.
Elektronska verzija: http://www.presek.si/31/1575-Petr.pdf
© 2004 Društvo matematikov, fizikov in astronomov Slovenije © 2010 DMFA - založništvo
ODKRITO NOVO NAJVEČJE (MERSENNOVO) PRAŠTEVILO
Števila, k katerimi štejemo, imenujemo naravna števila. Števila, ki imajo natanko dva različna delitelja, samega sebe in število 1, so prasteviia. Že pred več kot 2300 leti je Evklid dokazal, da je praštevil neskončno mnogo.
Število oblike 2n — 1 imenujemo Mereennovo število in ga označujemo z Mn. Ce je Mn praštevilo, ga imenujemo Aiersennovo praštevilo. Poglejmo, kakšno število je Mn, če je n sestavljeno število. Recimo, da je n enak zmnožku rs, potem lahko Mersennovo število \ln = Mrs zapišemo takole:
Mn = 2" - 1 = (2r - l)(2i,fs~1) + 2''(s"2> + ■ • ■ + 2r + 1) .
Vidimo, daje v tem primeru Mn produkt dveh števil, zato ni praštevilo. Torej velja, da če je Mn praštevilo, mora biti tudi n praštevilo. Mnogi so domnevah, da so vsa Mersennova števila Mn. kjer je n praštevilo, tudi prastevila. Leta 1536 je Hudalricus Regius pokazal, da 2n — 1 ni praštevilo (saj je enako zmnožku 23 in 89). Zgodovina iskanja naslednjih Mersennovih praštevil in velikih praštevil nasploh je pisana, o čemer smo v Preseku že pisali v članku P. Potočnik: Največja znana praštcvila -nekoč in danes. Presek 28 (2000/2001), 349-351. Domneva, da je tudi Mersennovih praštevil neskončno, ni dokazana.
17. novembra 2003 je računalnik študenta Michaela Shaferja na ekran zapisal sporočilo o najdbi novega, največjega znanega Mersennovega pra-števila
2209960U __ ^
ki je tudi največje znano praštevilo. Sestavlja ga kar 6 320 430 desetiških števk, v celoti pa si lahko to ogromno število ogledamo na medmrežnem naslovu
http://mersenne.org/prime6.txt.
Na Michaelovem računalniku je tekel program, ki ga dobimo na naslovu
http://www.mersenne.org
in je i/J io dišč na stran tako imenovanega velikega medmrežnega iskanja Mersennovih praštevil (GIMPS - Great Internet Mersenne Prime Search).
Program za iskanje Mersennovih praštevil je napisal ustanovitelj GIMPS George Woltman. Jedro programa predstavlja algoritem za hitro množenje velikih števil, ki ga je odkril matematik Richard Crandall, strojno in programsko opremo za porazdeljeno obdelovanje pa je dalo na razpolago podjetje Entropia inc. Vseh zadnjih šest največjih Mersennovih praštevil je bilo najdenih s pomočjo projekta GIMPS, ki traja že od januarja 19%. Vsako od njih je v času odkritja predstavljalo tudi največje znano praštevilo.
Najditelj 38. Mersennovega praštevila je dobil od organizacije Electronic Frontier Foundation (http://www.eff.org) nagrado 50000 ameriških dolarjev za odkritje praštevila z vsaj 1 000 000 števkami. Za odkritje praštevila z najmanj 10 000 000 števkami je razpisana nagrada v višini 100000 ameriških dolarjev. Sedaj poznamo 40 Mersennovih praštevil z naslednjimi potencami dvojke: 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213. 19937, 21701, 23209, 44497, 86243, J10503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917 in 2099G011. Ali sta števili Mi346tm7 in A^uaueoi i tudi 39. in 40. Mersennovi praštevil i, še ni ugotovljeno. Do sedaj so bile preverjene vse potence do 12 441 900, torej je še veliko kandidatov za nova Mersennova, praštevila, do zadnjega odkritega praštevila.
Za 10 000 000 števk bi morala biti potenca dvojke večja od 33 219 280. Projekt GIMPS se nadaljuje in sedaj čakamo na naslednje rekordno Mer-sennovo praštevilo. Ga bo našel kdo izmed vas?
Ciril Petr
Pred oddajo Preseka v tiskarno smo prejeli novico, daje bilo 15. maja 2004 odkrito novo največje (Marsennovo) praštevilo Ai2403658ai ki ga sestavlja 7 235 733 desetiških števk. O tem najnovejšem odkritju bomo še poročali v eni od naslednjih številk Preseka.