Project Euler 007 – Het 10.001ste priemgetal

Geplaatst op 22 augustus 2026 door admin

Probleemstelling

De eerste zes priemgetallen zijn 2, 3, 5, 7, 11 en 13. Het zesde priemgetal is dus 13.

Bepaal het 10.001ste priemgetal.

Eerste analyse

We onderzoeken de getallen in stijgende volgorde, testen welke getallen priem zijn en houden bij hoeveel priemgetallen we hebben gevonden. Zodra de teller 10.001 bereikt, kennen we het antwoord.

Een getal $n$ is priem wanneer het groter is dan 1 en geen positieve delers behalve 1 en zichzelf heeft. Bij de controle hoeven we mogelijke delers slechts tot en met $\sqrt n$ te testen.

Gekozen programmeeraanpak

De oplossing gebruikt de twee functies priem(n) en nde_priem(n).

priem(n) gaat na of een gegeven getal priem is. De functie behandelt 2 afzonderlijk, verwerpt andere even getallen en test daarna alleen oneven delers.
nde_priem(n) doorloopt de oneven kandidaten in stijgende volgorde, roept priem aan en stopt zodra het gevraagde aantal priemgetallen gevonden is.

Algoritme

Tel 2 als het eerste priemgetal.
Onderzoek achtereenvolgens de oneven getallen 3, 5, 7, enzovoort.
Test voor elke kandidaat de oneven delers tot en met zijn vierkantswortel.
Verhoog de teller wanneer de kandidaat priem is.
Stop zodra de teller 10.001 bedraagt.

Python-programma

import time
from math import isqrt


def priem(n: int) -> bool:
    """Ga na of n een priemgetal is."""
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False

    # Een samengesteld getal heeft minstens een deler tot en met sqrt(n).
    for deler in range(3, isqrt(n) + 1, 2):
        if n % deler == 0:
            return False

    return True


def nde_priem(n: int) -> int:
    """Bereken het n-de priemgetal, waarbij 2 het eerste is."""
    if n < 1:
        raise ValueError("n moet minstens 1 zijn")
    if n == 1:
        return 2

    aantal_priemgetallen = 1
    kandidaat = 1

    # Na 2 hoeven alleen oneven kandidaten onderzocht te worden.
    while aantal_priemgetallen < n:
        kandidaat += 2
        if priem(kandidaat):
            aantal_priemgetallen += 1

    return kandidaat


# Start van de tijdsmeting
starttijd = time.perf_counter()


# Bereken het 10.001ste priemgetal
antwoord = nde_priem(10_001)


# Stop de tijdsmeting
eindtijd = time.perf_counter()
uitvoeringstijd = eindtijd - starttijd


# Toon het resultaat
print(f"Het 10.001ste priemgetal is: {antwoord}")
print(f"Uitvoeringstijd: {uitvoeringstijd:.8f} seconden")

De eenvoudige bovengrens voor de tijdscomplexiteit is $O(p_n\sqrt{p_n})$ , waarbij $p_n$ het $n$ -de priemgetal is. Het geheugengebruik is $O(1)$ .

Wiskundige benadering

De priemgetal-telfunctie $\pi(x)$ telt hoeveel priemgetallen kleiner dan of gelijk aan $x$ zijn. Volgens de priemgetalstelling geldt

$\pi(x)\sim\frac{x}{\ln x}.$

Voor de omgekeerde vraag kunnen we gebruiken dat

$p_n\approx n(\ln n+\ln\ln n-1).$

Voor $n=10\,001$ geeft dit ongeveer 104.318. We verwachten het antwoord dus in de buurt van honderdduizend. Dit is een schatting; de exacte primaliteitstesten van het programma blijven nodig.

Resultaat

Het 10.001ste priemgetal is

$\boxed{104743}.$

Uitvoeringstijd: 0,05393281 seconden.

Besluit

De opsplitsing in priem(n) en nde_priem(n) levert een duidelijke en herbruikbare oplossing. Proefdeling is voor deze opgave ruim snel genoeg, terwijl de priemgetalstelling vooraf een goede schatting van de grootteorde geeft.

OMB Maxi finale 2026 vraag 2

Geplaatst op 16 augustus 2026 door admin

Drie onbekende priemgetallen hebben een som en een product die precies een factor 101 verschillen. Een groottevergelijking en een korte factorisatie blijken voldoende om het drietal uniek vast te leggen.

Infobox

Onderwerpen: Getaltheorie
Probleemoplossingstechnieken: Groottevergelijking, deelbaarheid, ontbinden in factoren, gevallenonderzoek
Moeilijkheid: Gemiddeld
Competitie: Olympiade Mathématique Belge, Maxifinale
Jaar: 2026
Opgavenummer: 2

Opgave

De getallen $p$ en $s$ zijn respectievelijk het product en de som van de drie priemgetallen $a$ , $b$ en $c$ . Een van de getallen $p$ en $s$ is gelijk aan 101 maal het andere. Bepaal $a$ , $b$ en $c$ .

Eerste idee

Vergelijk eerst het product met de som om te bepalen welke grootheid 101 maal de andere is. De factor 101 in het product dwingt daarna een van de drie priemgetallen gelijk te zijn aan 101. Met die waarde ingevuld, reduceert de opgave tot het onderzoeken van de factorparen van 102.

Uitwerking

We hebben

$p=abc \qquad\text{en}\qquad s=a+b+c.$

We tonen eerst aan dat $p>s$ . Voor $a=b=c=2$ geldt

$abc-(a+b+c)=8-6=2>0.$

Als een van de drie getallen toeneemt met een positief getal $d$ , terwijl de andere twee gelijk blijven, dan neemt $abc-(a+b+c)$ toe met

$d(uv-1),$

waarbij $u$ en $v$ de twee andere priemgetallen zijn. Omdat $u,v\ge 2$ , is $uv-1\ge 3>0$ . De uitdrukking $abc-(a+b+c)$ is dus in elk van de drie variabelen strikt stijgend. Bijgevolg geldt voor alle priemgetallen $a$ , $b$ en $c$ dat

$abc>a+b+c,$

en dus $p>s$ .

Daarom kan $s$ niet gelijk zijn aan $101p$ . De gegeven voorwaarde moet dus luiden

$p=101s.$

Bijgevolg

$abc=101(a+b+c).$

Hieruit volgt dat $101\mid abc$ . Omdat 101 een priemgetal is, deelt 101 volgens het lemma van Euclides minstens een van de priemgetallen $a$ , $b$ en $c$ . Een priemgetal dat deelbaar is door 101, moet zelf gelijk zijn aan 101. Door de symmetrie mogen we aannemen dat

$c=101.$

Invullen geeft

$101ab=101(a+b+101).$

Na delen door 101 vinden we

$ab=a+b+101.$

We herschrijven dit als

$ab-a-b=101$

en tellen aan beide kanten 1 op:

$(a-1)(b-1)=102.$

De positieve factorparen van

$102=2\cdot 3\cdot 17$

zijn, op volgorde van de kleinste factor,

$(1,102),\quad(2,51),\quad(3,34),\quad(6,17).$

We controleren ze allemaal:

$(a-1,b-1)=(1,102)$ geeft $(a,b)=(2,103)$ ; beide getallen zijn priem.
$(a-1,b-1)=(2,51)$ geeft $(a,b)=(3,52)$ ; 52 is niet priem.
$(a-1,b-1)=(3,34)$ geeft $(a,b)=(4,35)$ ; beide getallen zijn niet priem.
$(a-1,b-1)=(6,17)$ geeft $(a,b)=(7,18)$ ; 18 is niet priem.

Dus het enige mogelijke ongeordende drietal is

${a,b,c}={2,101,103}.$

Ter controle:

$s=2+101+103=206$

$p=2\cdot 101\cdot 103=20806=101\cdot 206=101s.$

De gezochte priemgetallen zijn bijgevolg, in willekeurige volgorde,

$\boxed{2,\ 101,\ 103}.$

Probleemoplossingstechnieken

Groottevergelijking: Het product is groter dan de som, zodat alleen $p=101s$ mogelijk is.
Deelbaarheid: De priemfactor 101 moet een van de drie priemgetallen zijn.
Ontbinden in factoren: De resterende vergelijking wordt $(a-1)(b-1)=102$ .
Gevallenonderzoek: Alle factorparen van 102 worden op primaliteit gecontroleerd.

Bron

Priemgetallen en Gilbreath

Geplaatst op 24 februari 2026 door admin

Sommige vermoedens in de getaltheorie zijn zo eenvoudig dat je ze in één minuut kunt uitleggen—en toch blijft een bewijs decennia (of eeuwen) buiten bereik. Het vermoeden van Gilbreath is zo’n voorbeeld.

In 1958 krabbelde de Amerikaanse wiskundige en goochelaar Norman Gilbreath(1936-) iets op een servetje en vond vervolgens een verbijsterende hypothese over priemgetallen:

Neem een rij opeenvolgende priemgetallen vanaf 2 en schrijf onder elk opeenvolgend tweetal de absolute waarde van hun verschil. In de derde rij neem je weer de positieve verschillen tussen opeenvolgende getallen, enzovoort. Gilbreaths vermoeden is dat elke rij vanaf de tweede begint met het getal 1.

Alle priemen behalve de eerste zijn oneven, dus de verschillen in de tweede rij zijn vrijwel altijd even. Dat verklaart waarom je veel ’s en ’s ziet in latere rijen. Maar “alles is meestal even” dwingt helemaal niet af dat het allereerste element in élke volgende rij precies $1$ blijft. Dat is het mysterieuze, hardnekkige deel. François Proth observeerde het al in de 19e eeuw; Norman L. Gilbreath maakte het in 1958 bekend (vandaar soms “Proth–Gilbreath”) en tot op heden is er nog geen bewijs van gevonden. Het patroon is zeer ver gecontroleerd door middel van computerberekeningen. Odlyzko had het in 1993 gecontroleerd voor alle priemen tot $10^{13}$

Mersenne priemgetallen

Geplaatst op 27 juli 2025 door admin

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 een priemgetal is én $2^ n-1$ óók een priemgetal oplevert, dan spreken we van een Mersenne-priemgetal.

Let op: niet elke waarde van 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 23 mei 2025 door admin

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

Wiskunde is leuk

Tag archieven: priemgetallen