Recursieve functie genereert priemgetallen
In 2003 ontdekten verschillende studenten op de New Kind of Science Summer School iets interessants aan de recursieve formule an = an-1 + ggd(n, an-1): wanneer je de reeks start met a1 = 7, dan blijken alle verschillen an - an-1 ofwel 1 ofwel een priemgetal te zijn. Met ggd bedoelen we hier de grootste gemene deler van twee gehele getallen. De rij an begint als volgt:
7, 8, 9, 10, 15, 18, 19, 20, 21, 22, 33, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 69, …
De opeenvolgende verschillen an - an-1 zijn:
1, 1, 1, 5, 3, 1, 1, 1, 1, 11, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 23, …
Als we nu de 1′en en de dubbels verwijderen, genereert deze lijst de volgende priemgetallen:
5, 3, 11, 23, 47, 101, 7, 13, 233, 467, 941, 1889, 3779, 7559, 15131, 53, 30323, …
Eén van die studenten van toen, Eric Rowland van Rutgers University, heeft nu na jaren zoeken kunnen bewijzen dat deze reeks effectief enkel priemgetallen en 1 genereert. Rowland heeft de formule de afgelopen vier jaar van tijd tot tijd proberen te bewijzen, maar eens hij het juiste inzicht kreeg, had hij binnen enkele dagen een schets van het bewijs en in enkele weken waren alle details uitgewerkt. Het bewijs is verrassend genoeg vrij elementair.
Voor de beginvoorwaarden a1 = 4 en a1 = 8 geldt hetzelfde resultaat. Met bepaalde beginvoorwaarden zoals a1 gelijk aan 532 of 801 komen er niet-priemgetallen in de reeks voor, maar Rowland vermoedt dat voor elke beginvoorwaarde er voor grote n enkel 1 of priemgetallen in de reeks voorkomen.
De Franse wiskundige Benoit Cloitre bewees onlangs van een andere gelijkaardige formule dat het een priemgetallengenerator is. Neem je de reeks b1 = 1 en bn = bn-1 + kgv(n, bn-1) voor n ≥ 2 en met kgv het kleinste gemeen veelvoud van twee gehele getallen, dan is bn/bn-1 - 1 gelijk aan 1 of een priemgetal.
Referenties:
- Eric Rowland, A Natural Prime-Generating Recurrence, Journal of Integer Sequences, Vol. 11 (2008)
- Jeffrey Shallit, Rutgers Graduate Student Finds New Prime-Generating Formula, Recursivity (20 juli 2008)
Wiskundemeisjes » Priemformule on 25 Jul 2008 at 10:13 am
[...] 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. [...]