Wiskundemeisjes

Ionica & Jeanine
 
Slik Internetbureau Rotterdam Internetbureau Rotterdam



  • Laatste Reacties

Categorieën

Archief

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.

nieuw

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:

7, 8, 9, 10, 15, 18, 19, 20, 21, 22, 33, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 69

en dit zijn de bijbehorende verschillen a(n) - a(n-1)

1, 1, 1, 5, 3, 1, 1, 1, 1, 11, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 23.

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

5, 3, 11, 23, 47, 101, 7, 13, 233, 467, 941, 1889, 3779, 7559, 15131, 53, 30323, ...


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!

18 reacties op “Priemformule”

  1. Arno van Asseldonk:

    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.

  2. Odette:

    In de Vlaamse handboeken noemt men een priemgetal een getal dat juist 2 positieve delers heeft, dus 1 is geen priemgetal.

  3. Rinse Poortinga:

    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.

  4. Proeme:

    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...

  5. Proeme:

    wat is eigenlijk de reden dat een priemgetal zo gedefinieerd wordt dat 1 geen priemgetal is?

  6. HJ:

    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.

  7. Rinse Poortinga:

    Proeme,inderdaad een slordigheidje van mij:

    Een priemgetal is een natuurlijk getal dat geen niet-triviale delers heeft.

  8. Rinse Poortinga:

    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.

  9. Rinse Poortinga:

    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.

  10. Arno van Asseldonk:

    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.

  11. Speicus:

    "n(1)=7", beginnen wiskundigen weer bij 1 te tellen en indexeren? Dat is toch tijden lang 0 geweest...

  12. Marco:

    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.

  13. Marco:

    @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.

  14. Rinse Poortinga:

    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.

  15. Marco:

    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

  16. Johan B.:

    @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.

  17. Rinse Poortinga:

    Dat bedoelde ik in nr8 met:

    "De reden van het uitzonderen van 1 zal wel zijn, dat dat eenvoudiger formuleringen van stellingen geeft."

  18. Willem Noorduin:

    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.

Plaats een reactie


Je kunt LaTeX gebruiken in je reactie.
Gelieve antwoorden op puzzels tussen [SPOILER] en [/SPOILER] te plaatsen.