Tag archieven: priemgetallen

Mersenne priemgetallen

Geplaatst op door

Een Mersenne-priemgetal is een speciaal soort priemgetal dat de vorm heeft:

    \[M_n=2^n-1\]

waarbij n een natuurlijk getal is. Bijvoorbeeld:

  • 2^2-1=3

  • 2^3-1=7

  • 2^5-1=31

Als zowel n een priemgetal is én 2^ n-1 óók een priemgetal oplevert, dan spreken we van een Mersenne-priemgetal.

Let op: niet elke waarde van n die priem is, levert automatisch een Mersenne-priemgetal op. Zo is  n = 11 een priemgetal, maar 2^{11}=2047=23*89 is geen priemgetal

De naam Mersenne verwijst naar de Franse monnik en wiskundige Marin Mersenne (1588–1648). In zijn tijd onderzocht hij priemgetallen van de vorm 2^n-1 en stelde hij een lijst samen van getallen waarvan hij dacht dat ze Mersenne-priemgetallen waren. Hoewel zijn lijst deels incorrect bleek (hij vergiste zich bij sommige waarden), werd zijn werk een belangrijk startpunt voor verder onderzoek naar deze getallen. Sindsdien zijn wiskundigen, zowel amateurs als professionals, gefascineerd geraakt door de unieke eigenschappen van Mersenne-priemgetallen.

In 1750 stelde Euler vast dat M_{31} priem was. In die tijd waren er 8 gekende Mersenne priemgetallen, voor p=2,3,5,7,13,17,19,31. M_{31} bleef ongeveer een eeuw het grootste gekende Mersenne priemgetal. In 1876 vond de Franse wiskundige Lucas (1842-1891) een grotere: M_{127}, een getal van 39 cijfers! De eerste 12 Mersenne priemgetallen (de 8 vorige en deze voor p=61,89,107 en p=127 ) werden allemaal met pen en papier berekend.

Met de komst van de eerste computers werden later ook priemen gevonden voor p=521,607,1279,2203,2281,3217,4253,4423,9689,9941,11213, met dank aan de Amerikaanse wiskundigen Lehmer en Robinson.

George Woltman, een software ontwikkelaar, richtte in 1996 het GIMPS-project (Great Internet Mersenne Prime Search) op, dat wereldwijd vrijwilligers laat meerekenen. Het GIMPS is verantwoordelijk voor het vinden van de grootste priemgetallen ooit ontdekt, allemaal Mersenne-priemgetallen.

Momenteel is zijn er 52 Mersenne priemen gevonden en het grootste is gevonden voor p=136279841.  Het werd ontdekt op 12 oktober 2024 door Luke Durant uit San José (Californië).

Om het aantal cijfers te berekenen van M_n, stellen we eerst vast dat M_n en M_n+1=2^n het zelfde aantal cijfers bevatten. Om het aantal cijfers van 2^n te bepalen , berekenen  we A=\log 2^n=n*\og 2\approx 0,30103*p. Voor bijvoorbeeld M_{11213}, vinden we A=3375,449... en dus dat M_{11213} bestaat uit 3376 cijfers.

Hieronder zie je de grafiek van de exponenten van ontdekte Mersenne-priemgetallen door de tijd heen. Eeuwenlang bleef de exponent laag (onder de 1000). Vanaf de 20e eeuw, en vooral sinds de oprichting van GIMPS (1996), is er een explosieve stijging te zien.

 

 

Priemgaten

Geplaatst op door

Het verschil tussen twee opeenvolgende priemgetallen wordt ook wel eens het priemgat genoemd. Wiskundigen hebben altijd geprobeerd om een systeem te vinden in de reeks priemgetallen 2,3,5,7,11,13,17,19,23,29,31,… Er werd lang gezocht naar de gaten die deze reeks bevat, dus de verschillen tussen twee opeenvolgende priemgetallen. De grootte van het gemiddelde gat groeit als het natuurlijke logaritme van de priemgetallen die het begrenzen. 

In 1985 formuleerde een Roemeens wiskundige Dorin Andrica(1956-) een eigenschap over deze gaten. Het is weer te geven als :

Hierbij zijn p_n en p_{n+1} twee opeenvolgende priemgetallen en stelt het linkerlid dus het priemgat voor. Dit resultaat is tot op heden niet bewezen voor alle priemgetallen, maar er is ook nog geen tegenvoorbeeld gevonden.

Het vermoeden van Andrika  beperkt de maximale grootte van priemgaten: hoewel priemgaten steeds groter worden naarmate priemgetallen groter worden, suggereert het vermoeden dat ze nooit sneller groeien dan ongeveer \sqrt{p_n}.

 

Priemgetallen

Geplaatst op door

De Poolse wiskundige W.Sierpinski (1882-1969) was eer gefascineerd door de priemgetallen en hun spreiding tussen de andere natuurlijke getallen. We vermelden twee mooie resultaten.

Men kan een rij van opeenvolgende natuurlijke getallen bepalen, zo lang als men wilt, die geen enkel priemgetal bevat. Zo kan men bijvoorbeeld 100 opeenvolgende getallen kiezen zonder dat er een priemgetal inzit.  Neem 101!+2,101!+3,…,101!+101. Dit zijn 100 opeenvolgende getallen en ze zijn geen van allen priem want ze zijn respectievelijk deelbaar door 2,3,…,101

Voor elke n kan men een priemgetal vinden met links en rechts ervan n niet-priemen:

  • Neem een priemgetal q groter dan n+1.
  • Bereken a=\prod_{j=1}^{q-2}(q^2-j^2).
  • q  is onderling ondeelbaar met a.
  • De stelling van Lejeune-Dirichlet over de rekenkundige rij zegt dat er een priemgetal p bestaat met p>q en p=ak+q.
  • Nu is q+j een deler van a en omdat p+j=ak+q+j ook een deler van p+j. 
  • Analoog is q-j een deler van p-j.
  • Dus zijn p-j en p+j niet priem en dit voor j=1,2,…,n

Neem n=2 en q respectievelijk de priemgetallen 5,7,11,13,…, dan kan je zo bewijzen dat er oneindig veel priemgetallen bestaan die geen deel uitmaken van een priemtweeling.

Spiraal van Ulam

Geplaatst op door

Je kan volgend rooster van natuurlijke getallen maken in de vorm van een spiraal:

De wiskundige Stanislaw Ulam kreeg in 1963 het idee om e priemgetallen hierbij aan te duiden 

Hij zag, tot zijn verbazing, dat de priemgetallen de neiging hebben om zich op diagonalen van de spiraal te bevinden. De diagonalen zijn ook zichtbaar wanneer er heel veel getallen in een spiraal worden geplaatst. Het opvallende is, dat priemgetallen zich meer op bepaalde diagonalen bevinden dan op andere. De reden hiervoor is alsnog onduidelijk.