Op zoek naar grote priemgetallen

Het GIMPS project

Bergbeklimmers hebben een voor velen onbegrepen drang om de hoogste berg te beklimmen. Zo zijn er andere gekken die een zelfde drang voelen bij de beklimming van hele grote getallen. Eén verschil: bergen hebben een eindige hoogte, het hoogste is theoretisch te halen, getallen kunnen oneindig groot worden. Je kan dus eindeloos blijven zoeken naar getallen met een bijzondere eigenschap en je kan je blijven afvragen of er nog grotere getallen zijn met die eigenschap. Een oneindigheid in een oneindige ruimte.

Priemgetallen

Een van de bijzondere getallen waar wiskundigen in geïnteresseerd zijn, zijn priemgetallen. Priemgetallen zijn getallen die alleen deelbaar zijn door 1 en zichzelf. De eerste priemgetallen zijn 2, 3, 5, 7, 11, 13, 17, … Hele grote priemgetallen hebben tegenwoordig nog praktische nut. Zij worden gebruikt bij algoritmes voor versleuteling van berichten. Hierbij gaat het dan wel om grote priemgetallen (grootte orde 2¹⁵⁶) maar nog niet om hele grote getallen_, zo groot als het GIMPS project zoekt.

Mersenne priemgetallen

Om te bepalen of grote getallen priemgetallen zijn heb je krachtige computers nodig of een hele boel kleine computers. GIMPS probeert zoveel mogelijk gewone PC's te gebruiken en zij zoeken die in de hele wereld. Iedereen kan mee doen. Ook jij! GIMPS betekent dan ook "Great Internet Mersenne Prime Search". GIMPS zoekt niet naar zo maar willekeurige priemgetallen, maar naar "alle" priemgetallen die geschreven kunnen worden als 2ⁿ-1. Dit zijn de zogenoemde "Mersenne Priemgetallen". De eerste kan je nog wel snel zelf vinden, hoewel het al snel lastig wordt om te bepalen of je te maken hebt met een priemgetal. De Franse monnik Marin Mersenne (1588-1648) heeft een (mislukte!) poging gedaan om de getallen te vinden met de eigenschap dat 2ⁿ-1 een priemgetal is. Hij is gekomen tot n=257. Ondanks dat hij een foutieve reeks vond, zijn deze priemgetallen toch naar hem genoemd.

 Rekenen met z'n allen

Om nu te bepalen of bijvoorbeeld 3863687 ook tot de reeks behoort, laat ik mijn computer dag en nacht aan staan. Op de achtergrond slokt het programma Prime95 al mijn niet gebruikte CPU-kracht op om na ongeveer 12 dagen uitsluitsel te geven. En ik doe dat niet alleen, maar nog 3000 mensen over de hele wereld rekenen aan evenveel getallen. In 1996 is het project begonnen en toen hoopte men In het jaar 2000 alle getallen kleiner dan 5,260,000 doorgerekend te hebben. Nu hoeven we gelukkig niet alle getallen door te rekenen, maar alleen de priemgetallen. Dus moeten we wel alle priemgetallen kennen tot 5,260,000. De doelstelling is ruimschoots gehaald door de vele gebruikte computers en omdat computers veel krachtiger zijn geworden dan eerst gedacht. De volgende doelstelling is het 41ste getal en nog liever een Mersenne priemgetal van 10 miljoen cijfers.

 Perfecte getallen

Een op het eerste oog onverwacht broertje van de Mersenne priemgetallen zijn de Perfecte getallen en deze kunnen ons bijzonder goed helpen om heel veel sneller te bepalen of een Mersenne getal ook werkelijk een priemgetal is. Een perfect getal is een getal dat gelijk is aan de som van zijn delers. Zes is het eerste perfecte getal, want 6=1+2+3 (en is deelbaar door 1, 2 en 3) en 28 het tweede 28=1+2+4+7+14. De volgende zijn 496 en 8128. Nu kan je bewijzen dat elk perfect getal te schrijven is in de vorm 2^n-1( 2ⁿ-1), waarbij ( 2ⁿ-1) altijd een priemgetal is. Onze Mersenne priemgetallen!

Nu kan het bewijs dat een getal een Mersenne priemgetal is ook geleverd worden als we kunnen bepalen of het bijbehorende perfecte getal inderdaad perfect is. Met de Lucas-Lehmer test kan dat dan op een Pentium200 met de snelheid van ongeveer n*0.27 seconde (voor n is ongeveer 3,8 miljoen; voor n=4,8 miljoen is het al 0.35 sec).

 Nog wat geschiedenis

Zoals reeds vermeld vond Hudalricus Regius dat 11 niet tot de Mersenne reeks behoort. In 1603 berekende Pietro Cataldi dat 17, 19, 23, 29, 31, 37 ook tot de reeks behoren. En het leek erop dat 11 een uitzondering was en dat alle andere priemgetallen wel tot de Mersenne reeks behoren. Maar in 1640 bewees Format dat 23 en 37 incorrect zijn en in 1738 was het Euler die ook 29 schrapte uit de lijst. Hij bevestigde wel 31. Mersenne rapporteerde in 1644 over 31, 67, 127 en 257 en claimde dat alle andere getallen kleiner dan 257 niet tot de reeks behoren. Ook hij zat er behoorlijk naast. De reeks moet zijn:

n = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127

Dit was allemaal in 1876 bekend. Verder was het onmogelijk om nog handmatig grotere getallen uit te rekenen en we moesten wachten op computers om de reeks verder op te bouwen. In 1952 werd dan eindelijk het 13e getal gevonden en in 2001 het 39e. Tot en met het 37e getal weten we ook dat alle tussenliggende getallen geen Mersenne priemgetal opleveren.

Als je de hele lijst met bekende Mersenne priemgetallen wilt zien, klik dan hier ...

Je kan zelfmeedoen

Het is eenvoudig om je aan te sluiten bij GIMPS. Het werkt als volgt. Je zoekt op Internet pagina www.mersenne.org/prime.htm. Van daaruit kan je de software downloaden. Verder gaat het als vanzelf. Het programma haalt zelf van Internet, zodra je verbinding hebt gemaakt, de getallen op die aan jou worden toegewezen en rapporteert terug naar GIMPS.

Het programma PRIME95 draait zonder problemen op Windows95/98, WindowsNT, Windows 2000, Windows XP, maar ook voor andere operatingsystemen zijn er versies beschikbaar. Je kan zorgen dat bij het inloggen op je systeem het programma automatisch opstart. Een icoontje rechtsonder, naast het klokje, is het enige dat je ziet. Als je uitlogt of het programma stopt wordt het tussenresultaat opgeslagen. Dit gebeurt trouwens elk half uur. Je merkt er verder niets van dat dit programma op de achtergrond draait. Alleen zal je CPU altijd voor 100% bezet zijn. Heb je hem tenminste nog ergens voor gekocht.

Wat levert het op?

Eeuwige roem!! Als een van de door jou gekozen getallen inderdaad een nieuw Mersenne priemgetal oplevert zal jouw naam daaraan verbonden worden. Bovendien ontvang je $1 voor elke1000 cijfers van het priemgetal; dat zou dus ongeveer $1000 moeten opleveren. Voor een priemgetal met 1 miljoen cijfers ontvang je maar liefst $100,000. Lijkt me de moeite waard!

Het programma is tevens een goede test of je computer geen fouten in de hardware heeft. Het programma wordt ook door Intel gebruikt om elke Pentium te testen voor het de fabriek uitgaat.

Enige belangrijke links

update 10nov01