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!
vrijdag 25 juli 2008 om 12:53
Dat 1 niet als een priemgetal wordt beschouwd wordt duidelijker als je Fermats definitie van een priemgetal hanteert: een priemgetal p is een natuurlijk getal groter dan 1 met de eigenschap dat p alleen zichzelf en 1 als deler heeft. Uit het gegeven dat p groter dan 1 is volgt dan automatisch het gegeven dat 1 niet als een priemgetal wordt beschouwd.
vrijdag 25 juli 2008 om 18:32
In de Vlaamse handboeken noemt men een priemgetal een getal dat juist 2 positieve delers heeft, dus 1 is geen priemgetal.
vrijdag 25 juli 2008 om 22:16
Nog een alternatief:
Dat een natuurlijk getal deelbaar is door 1 en door zichzelf is triviaal. Een priemgetal is een natuurlijk getal zonder triviale delers.
zaterdag 26 juli 2008 om 00:31
Rinse, klopt die wel?
"zonder triviale delers" komt op mij over als "niet deelbaar door 1 en door zichzelf". Maar elk getal is deelbaar door 1 en door zichzelf...
zaterdag 26 juli 2008 om 00:31
wat is eigenlijk de reden dat een priemgetal zo gedefinieerd wordt dat 1 geen priemgetal is?
zaterdag 26 juli 2008 om 02:45
Technische redenen, inderdaad. Zo geldt bijvoorbeeld de stelling dat elk geheel getal een unieke priemgetallen ontbinding heeft (op volgorde na). Als 1 ook een priemgetal zou zijn, is het aantal delers 1 niet echt uniek vastgelegd.
zaterdag 26 juli 2008 om 11:46
Proeme,inderdaad een slordigheidje van mij:
Een priemgetal is een natuurlijk getal dat geen niet-triviale delers heeft.
zaterdag 26 juli 2008 om 13:06
Onder de definitie van nr7 zou ook het getal 1 vallen.Dus het getal 1 toch maar expliciet uitzonderen? Is er eigenlijk wel een principiële reden om 1 niet tot de priemgetallen te rekenen? In de wikipedia lees ik dat Henri Lebesgue 1 wel tot de priemgetallen rekende en dat is toch niet de minste. De reden van het uitzonderen van 1 zal wel zijn, dat dat eenvoudiger formuleringen van stellingen geeft.
zaterdag 26 juli 2008 om 13:24
De relatie 'x deelt y' is een partiële ordening van de natuurlijke getallen ongelijk 0. In deze partiële ordening is 1 het kleinste element en de priemgetallen zijn de onmiddellijke opvolgers van 1.
zaterdag 26 juli 2008 om 13:26
Met behulp van het begrip triviale deler kunnen we het begrip priemgetal als volgt definiëren: als p een natuurlijk getal groter dan 1 is en alleen de triviale delers 1 en p als deler heeft, dan is p een priemgetal.
dinsdag 29 juli 2008 om 13:50
"n(1)=7", beginnen wiskundigen weer bij 1 te tellen en indexeren? Dat is toch tijden lang 0 geweest...
dinsdag 29 juli 2008 om 14:38
Leuk! Die rij staat natuurlijk bomvol enen en er zijn veel makkelijkere en snellere manieren om priemgetallen te maken, maar het is heel leuk om te zien dat er functies zijn die af en toe getallen uitspugen waarvan je weet dat ze priem zijn zonder het te hoeven testen! Het gebruiken van de ggd komt op mij wel een beetje over als valsspelen...
Tsja, Speicus, er zijn hier geen vaste regels voor. Er is nog nooit een wiskundige op de brandstapel beland door het beginnen te indexeren bij 0 of juist bij 1 (toch? anders gebeurt het tegenwoordig in ieder geval niet meer, stenigen schijnt nu veel populairder te zijn.)
Wat het handigst is hangt af van het soort rij. Als je bij 1 begint heb je het voordeel dat a(k) ook echt het k-de getal in de rij is en niet het (k+1)-ste. Wie bij nul begint, werpe de nulde steen.
dinsdag 29 juli 2008 om 14:44
@Rinse Poortinga. Een voorbeeld van een principiele reden om 1 niet tot de priemgetallen te rekenen is "unieke priemfactorizatie." Als je het getal 1 een priemgetal noemt, dan zijn getallen niet meer uniek te schrijven als produkt van priemgetallen, want 6=2*3=1*2*3=1*1*2*3=1*1*1*2*3.
dinsdag 29 juli 2008 om 15:48
Marco: dat probleem kan ook anders opgelost worden. Je zegt dan gewoon dat ieder natuurlijk getal groter dan 1 uniek te schrijven is als een product van priemgetallen groter dan 1.
dinsdag 29 juli 2008 om 17:35
Rinse Poortenga: Zeker, en dat is het mooie van principiele redenen. Niemand heeft echt gelijk. Ik vind echter dat jouw zin iets kunstmatigs heeft door het feit dat er twee keer "groter dan 1" in staat. En dat terwijl deze zin een van de belangrijkste eigenschappen van priemgetallen is!
Ik ben trouwens ooit eens per ongeluk op de volgende pagina beland waar uitgelegd wordt waarom 1 juist wel een priemgetal is volgens God.
http://www.fivedoves.com/revdrnatch/Does_God_think_1_is_prime.htm
dinsdag 29 juli 2008 om 17:35
@Rinse: Als je elke keer "priemgetal groter dan 1" moet schrijven in elke zinnige uitspraak over priemgetallen, dan gedraagt 1 zich blijkbaar zodanig anders dat het beter is om 1 maar geen priemgetal te noemen.
dinsdag 29 juli 2008 om 21:08
Dat bedoelde ik in nr8 met:
"De reden van het uitzonderen van 1 zal wel zijn, dat dat eenvoudiger formuleringen van stellingen geeft."
zondag 3 augustus 2008 om 16:38
Cool. Following the discussions I can add: When 1 is prime, there ought to be the field F_1 of 1 element. Okay, Okay, we all know that a field has to be something with >= 2 elements, but you can find evidence on the web (just Google "field of one element") that something like this must exit, if we generalize other ideas.
A fine paper to read is "New Approach to Arakelov Geometry" of Nikolai Durov, difficult, but fine.
What d'ya know: even mathematics has an occult branch.