Internetbureau Rotterdam 
Dit bericht is geplaatst op vrijdag 25 juli 2008 om 11:12 in categorieën Nieuws. Je kunt de reacties volgen via een RSS 2.0 feed. Je kunt een reactie plaatsen, of een trackback van je eigen site plaatsen.
Wiskundemeisjes
Ionica & Jeanine
Priemformule
In Nieuws, door Ionica
Jeffrey Shallit schrijft op zijn onvolprezen blog Recursivity over een nieuwe formule om priemgetallen te genereren. Koen schreef hier ook al over. Weten jullie allemaal nog wat priemgetallen zijn? Dat zijn de getallen die alleen deelbaar zijn door één en zichzelf: bijvoorbeeld 2, 3, 5, 7 of 5417. Om technische redenen noemen we 1 geen priemgetal.
Priemgetallen worden al heel lang bestudeerd. We weten al meer dan tweeduizend jaar dat er oneindig veel priemgetallen bestaan en de zeef van Eratosthenes om priemgetallen te vinden is ongeveer even oud. Je zou misschien denken dat we alles wel zo'n beetje weten over priemgetallen. Niets is minder waar. Het vermoeden van Goldbach, de Riemann-hypothese en allerlei andere vermoedens over priemgetallen zijn nog steeds onbewezen.
Het is daarom enigszins verrassend als er iets nieuws over priemgetallen wordt ontdekt dat tamelijk eenvoudig is. Zoals deze formule om priemgetallen te genereren. Neem a(1) = 7 en neem voor n ≥ 2
a(n) = a(n-1) + ggd(n,a(n-1)).
Dat ggd is een afkorting voor de grootste gemene deler . Dus we vinden bij de eerste stap a(2) = a(1) + ggd(2,7) = 8. De verschillen tussen twee opeenvolgende termen a(n) - a(n-1) geven priemgetallen (en een heleboel enen).
De reeks a begint zo:
en dit zijn de bijbehorende verschillen a(n) - a(n-1)
Als we de enen overslaan, dan krijgen we de priemgetallen 5, 3, 11, 3 en 23. Als je zo verder gaat, dan vinden we (zonder de dubbelen en de enen) meer priemgetallen
Eric Rowland bewijst in het artikel A Natural Prime-Generating Recurrence dat in deze reeks alleen enen en priemgetallen voorkomen. Dit artikel is deze maand gepubliceerd in Journal of Integer Sequences. In het stuk van Shallit kun je meer lezen over de ontdekking van deze formule.
Er zijn trouwens nog een paar interessante open vragen bij de nieuwe formule. Werkt het bijvoorbeeld ook voor andere beginwaarden dan a(1) = 7? Voor a(1) = 532 (om maar wat te noemen) krijg je bijvoorbeeld vrij snel een 9. Rowland vermoedt echter dat voor elke begingetal er na een eindig aantal stappen alleen nog enen en priemgetallen komen. Nog interessanter is volgens mij de vraag of ook alle oneven priemgetallen voorkomen in zo'n reeks. Rowland vermoedt van wel...
Shallit had ons trouwens zelf gemaild over dit nieuwe resultaat. We zouden het heel leuk vinden als meer wiskundigen ons zouden tippen over ontwikkelingen die interessant zijn om hier te noemen!
