Je leest:

Nieuw algoritme vindt priemrij

Nieuw algoritme vindt priemrij

Priemgetallen zoeken is een heidens karwei: wiskundigen vissen naar getallen van soms miljoenen cijfers lang. In de getallenzee komen ook regelmatige reeksen van priemgetallen voor. Drie wiskundigen wisten een rij van 23 priemen lang te vinden.

Markus Frind, Paul Jobling en Paul Underwood zijn de gelukkige ‘eigenaars’ van AP-23, de eerste rekenkundige rij van 23 priemgetallen lang. Een rekenkundige rij is een reeks cijfers die telkens even ver van elkaar liggen, zoals 2,6,10,14,18. De vondst van de drie komt 11 jaar na de ontdekking van AP-22. Om de rij getallen te vinden moesten de drie wiskundigen bestaande zoekmethodes aanpassen. En passant vonden ze ook nog een extra stel rijen van 22 priemgetallen lang.

Rekenkundige priemrij

Rekenkundige rijen zijn er maar genoeg; met een basisgetal en stapgrootte is zo’n rij al gedefinieerd. Interessanter wordt het, als de getallen in de rij ook nog eens priemgetallen moeten zijn. Sinds 1993 stond het record voor zo’n rij op 22 priemgetallen. Frind, Jobling en Underwood hebben dat record verbroken. Ze gaven de volgende formule voor hun rekenkundige rij: 56.211.383.760.397 + K x 44.546.738.095.860. K kan hier voor de getallen 0 t/m 22 staan; voor K=23 geeft de formule geen priemgetal meer. Dat getal, 1.080.786.359.965.177, is namelijk gelijk aan: 29 * 37 * 61 * 83 * 271 * 734113.

De drie vonden deze rij door een enorme hoeveelheid potentiële rijen door een ‘zeef’ te halen. Dat is een wiskundige procedure die een hoop niet-priemgetallen uit de massa kanshebbers filtert. “We begonnen hiermee in 2002”, zegt Frind. “De algoritmes van toen konden AP-23 nooit in een redelijke tijd vinden.” Door op slimme manieren getallen uit te sluiten wisten de drie in twee jaar tijd de nieuwe recordrij te vinden. Overigens is het vinden van de priemrij veel moeilijker dan het testen van de rij: in 0,03 seconden weet het programma Mathematica te testen dat de 23 getallen allemaal priemen zijn!

De zeef van Eratosthenes stamt al uit de derde eeuw vóór Christus. Door telkens veelvouden van bekende priemgetallen weg te strepen, worden de niet-priemen gewied. De overgebleven getallen – hier tussen 1 en 64 – zijn allemaal priemen. bron: www.mathforum.org

Rijen van elke mogelijke lengte

Terence Tao en Ben Green bewezen onlangs een oud vermoeden over rekenkundige priemrijen. Ze lieten zien dat rekenkundige rijen van alle mogelijke lengtes bestaan; er is er dus minstens één van 2000 cijfers lang, bijvoorbeeld. Hoe je die opspoort is trouwens weer een heel ander verhaal!

Het grootste bekende priemgetal is een Mersenne-getal. Mersenne-getallen hebben de vorm 2X – 1, waarbij X zelf ook weer een priemgetal is. Niet alle X-en leveren een Mersenne-priem op. In mei 2004 werd de 41e gevonden: 2[^ 24.036.583^] – 1 is meer dan tien miljoen cijfers lang!

Dit artikel is een publicatie van NEMO Kennislink.
© NEMO Kennislink, sommige rechten voorbehouden
Dit artikel publiceerde Kennislink 13 jaar geleden

Discussier mee

Vragen, opmerkingen of bijdragen over dit artikel of het onderwerp? Neem deel aan de discussie.

LEES EN DRAAG BIJ AAN DE DISCUSSIE