Project Euler 005 – Kleinste veelvoud

Geplaatst op 8 augustus 2026 door admin

Probleemstelling

Het getal 2520 is het kleinste positieve getal dat zonder rest deelbaar is door elk getal van 1 tot en met 10.

Bepaal het kleinste positieve getal dat zonder rest deelbaar is door elk getal van 1 tot en met 20.

Eerste analyse

Alle veelvouden van 20 uitproberen is mogelijk, maar vereist zeer veel deelbaarheidstests. Het gevraagde getal is precies het kleinste gemene veelvoud van de getallen 1 tot en met 20. We kunnen dit kgv snel opbouwen met behulp van de grootste gemene deler.

Gekozen programmeeraanpak

Voor twee positieve gehele getallen $a$ en $b$ geldt

$\operatorname{kgv}(a,b)=\frac{a\cdot b}{\operatorname{ggd}(a,b)}.$

De grootste gemene deler berekenen we met het algoritme van Euclides. Daarna verwerken we achtereenvolgens alle getallen van 2 tot en met 20. Het lopende resultaat is na iedere stap het kleinste gemene veelvoud van alle getallen die tot dan toe zijn verwerkt.

Waarom het algoritme van Euclides werkt

Voor gehele getallen $a$ en $b$ , met $b\ne0$ , geldt

$\operatorname{ggd}(a,b)=\operatorname{ggd}(b,a\bmod b).$

Volgens de deling met rest kunnen we namelijk schrijven

$a=qb+r,$

waarbij $r=a\bmod b$ . Een getal $d$ deelt precies dan zowel $a$ als $b$ , als $d$ zowel $b$ als $r$ deelt:

als $d\mid a$ en $d\mid b$ , dan deelt $d$ ook $r=a-qb$ ;
omgekeerd, als $d\mid b$ en $d\mid r$ , dan deelt $d$ ook $a=qb+r$ .

De paren $(a,b)$ en $(b,r)$ hebben bijgevolg exact dezelfde gemeenschappelijke delers en dus dezelfde grootste gemene deler.

De Python-functie

def ggd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

past deze identiteit telkens opnieuw toe door $(a,b)$ te vervangen door $(b,a\bmod b)$ . De ggd verandert daarbij niet. De resten zijn steeds niet-negatief en strikt kleiner dan de vorige positieve deler. Daarom wordt uiteindelijk rest 0 bereikt. Dan geldt $\operatorname{ggd}(a,0)=a$ , zodat de overblijvende waarde van $a$ de grootste gemene deler is.

Een kort voorbeeld is

$\operatorname{ggd}(48,18) =\operatorname{ggd}(18,12) =\operatorname{ggd}(12,6) =\operatorname{ggd}(6,0) =6.$

Algoritme

Maak een functie die met het algoritme van Euclides de grootste gemene deler berekent.
Stel het lopende kleinste gemene veelvoud gelijk aan 1.
Doorloop de getallen van 2 tot en met 20.
Bereken telkens het nieuwe kgv met de ggd-formule.
Druk na de laatste stap het antwoord en de uitvoeringstijd af.

Python-programma

import time


# Bereken de grootste gemene deler met het algoritme van Euclides
def grootste_gemene_deler(eerste_getal, tweede_getal):
    while tweede_getal != 0:
        eerste_getal, tweede_getal = tweede_getal, eerste_getal % tweede_getal

    return eerste_getal


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


# Bouw het kleinste gemene veelvoud van de getallen 1 tot en met 20 op
kleinste_gemene_veelvoud = 1

for getal in range(2, 21):
    kleinste_gemene_veelvoud = (
        kleinste_gemene_veelvoud
        * getal
        // grootste_gemene_deler(kleinste_gemene_veelvoud, getal)
    )


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


# Toon het resultaat
print(f"Het kleinste positieve deelbare getal is: {kleinste_gemene_veelvoud}")
print(f"Uitvoeringstijd: {uitvoeringstijd:.8f} seconden")

Wiskundige oplossing

Het kgv bevat van elke priemfactor de hoogste macht die nodig is voor de getallen tot en met 20. Dit geeft

$2^4\cdot3^2\cdot5\cdot7\cdot11\cdot13\cdot17\cdot19 =232792560.$

Resultaat

Het kleinste positieve getal dat deelbaar is door alle getallen van 1 tot en met 20 is

$\boxed{232792560}.$

Uitvoeringstijd: minder dan 0,001 seconden.

Besluit

De combinatie van de kgv-formule en het algoritme van Euclides vermijdt een lange brute-force zoekactie. Zo wordt het correcte antwoord met een korte, algemene en leesbare methode berekend.

Project Euler 004 – Grootste palindroomproduct

Geplaatst op 7 augustus 2026 door admin

Probleemstelling

Een palindroomgetal leest van links naar rechts hetzelfde als van rechts naar links. Het grootste palindroom dat het product is van twee tweecijferige getallen is

$9009=91\cdot99.$

Bepaal het grootste palindroom dat geschreven kan worden als het product van twee driecijferige getallen.

Eerste analyse

Er zijn 900 driecijferige getallen. Zelfs wanneer we alle unieke paren onderzoeken, zijn er hoogstens 405450 producten. Deze zoekruimte is klein genoeg voor brute force.

We doorlopen de factoren in dalende volgorde, zodat grote producten eerst worden onderzocht. Zodra verdere producten niet meer groter kunnen zijn dan het beste gevonden palindroom, stoppen we de betreffende lus.

Gekozen programmeeraanpak

De eerste factor daalt van 999 tot 100. De tweede factor daalt telkens van 999 tot de eerste factor, zodat elk ongeordend factorpaar hoogstens eenmaal wordt onderzocht.

Een product is een palindroom wanneer zijn tekstvorm gelijk is aan diezelfde tekst in omgekeerde volgorde. Wanneer dat zo is en het product groter is dan het vorige resultaat, bewaren we het product en beide factoren.

Algoritme

Initialiseer het grootste palindroom met 0.
Doorloop de eerste factor dalend van 999 tot en met 100.
Doorloop de tweede factor dalend van 999 tot en met de eerste factor.
Bereken het product.
Breek de lus af wanneer geen groter product meer mogelijk is.
Vergelijk de tekstvorm van het product met de omgekeerde tekstvorm.
Bewaar elk groter gevonden palindroom en zijn factoren.
Druk het antwoord, de factoren en de uitvoeringstijd af.

Python-programma

import time


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


# Zoek dalend naar het grootste palindroomproduct
grootste_palindroom = 0
eerste_factor = 0
tweede_factor = 0

for factor_a in range(999, 99, -1):
    if factor_a * 999 <= grootste_palindroom:
        break

    for factor_b in range(999, factor_a - 1, -1):
        product = factor_a * factor_b

        if product <= grootste_palindroom:
            break

        product_als_tekst = str(product)

        if product_als_tekst == product_als_tekst[::-1]:
            grootste_palindroom = product
            eerste_factor = factor_a
            tweede_factor = factor_b


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


# Toon het resultaat
print(f"Het grootste palindroom is: {grootste_palindroom}")
print(f"Factoren: {eerste_factor} en {tweede_factor}")
print(f"Uitvoeringstijd: {uitvoeringstijd:.8f} seconden")

Wiskundige achtergrond

Een zescijferig palindroom heeft de vorm $abccba$ . De waarde ervan is

$100001a+10010b+1100c =11(9091a+910b+100c).$

Ieder zescijferig palindroom is dus deelbaar door 11. Bij een product dat zo’n palindroom vormt, moet minstens een van beide factoren deelbaar zijn door 11. De Python-oplossing hoeft deze extra eigenschap niet te gebruiken, omdat de gewone afkappingen de zoekruimte al voldoende beperken.

Resultaat

Het grootste palindroomproduct is

$906609=913\cdot993.$

Uitvoeringstijd: ongeveer 0,00099893 seconden.

Besluit

De dalende brute-force aanpak onderzoekt een beperkte zoekruimte en slaat dankzij de afkappingen veel onnodige producten over. Zo vinden we met duidelijke Python-code snel het correcte antwoord 906609.

Project Euler 003 – Grootste priemfactor

Geplaatst op 7 augustus 2026 door admin

Probleemstelling

De priemfactoren van 13195 zijn 5, 7, 13 en 29.

Wat is de grootste priemfactor van het getal 600851475143?

Eerste analyse

Alle getallen tot 600851475143 testen zou bijzonder traag zijn. Met proefdeling hoeven we slechts mogelijke factoren te onderzoeken. Wanneer we een factor vinden, delen we die volledig uit het getal, zodat het resterende getal en de te onderzoeken grens steeds kleiner worden.

Gekozen programmeeraanpak

We verwijderen eerst alle factoren 2. Daarna testen we alleen oneven delers vanaf 3. Iedere gevonden deler wordt zo vaak mogelijk uit het resterende getal gedeeld en wordt als voorlopig grootste priemfactor bewaard.

Zodra het kwadraat van de kandidaat-deler groter is dan het resterende getal, zijn geen kleinere factoren meer mogelijk. Een resterende waarde groter dan 1 is dan zelf priem en vormt de grootste priemfactor.

Algoritme

Stel het resterende getal gelijk aan 600851475143.
Deel factor 2 volledig uit.
Test daarna uitsluitend oneven delers vanaf 3.
Deel elke gevonden factor volledig uit en bewaar hem.
Stop zodra het kwadraat van de deler groter is dan het resterende getal.
Gebruik een eventueel resterend getal groter dan 1 als grootste priemfactor.
Druk het antwoord en de uitvoeringstijd af.

Python-programma

import time


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


# Zoek de grootste priemfactor met proefdeling
getal = 600_851_475_143
resterend_getal = getal
grootste_priemfactor = 1

while resterend_getal % 2 == 0:
    grootste_priemfactor = 2
    resterend_getal //= 2

deler = 3

while deler * deler <= resterend_getal:
    while resterend_getal % deler == 0:
        grootste_priemfactor = deler
        resterend_getal //= deler

    deler += 2

if resterend_getal > 1:
    grootste_priemfactor = resterend_getal


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


# Toon het resultaat
print(f"De grootste priemfactor is: {grootste_priemfactor}")
print(f"Uitvoeringstijd: {uitvoeringstijd:.8f} seconden")

Wiskundige achtergrond

Volgens de hoofdstelling van de rekenkunde kan ieder natuurlijk getal $n>1$ , op de volgorde van de factoren na, op unieke wijze geschreven worden als een product van priemgetallen:

$n=p_1^{a_1}p_2^{a_2}\cdots p_r^{a_r}.$

Project Euler 003 komt dus neer op het bepalen van de priemfactorontbinding van $600851475143$ en vervolgens het kiezen van de grootste priemfactor.

Controle met wiskundige software

Ter controle kan de volledige priemfactorontbinding met factorint uit SymPy worden bepaald:

from sympy import factorint

factorisatie = factorint(600851475143)
print(factorisatie)

SymPy geeft als uitvoer:

{71: 1, 839: 1, 1471: 1, 6857: 1}

In gewone wiskundige notatie is dit

$600851475143=71\cdot839\cdot1471\cdot6857.$

SymPy wordt hier alleen gebruikt als onafhankelijke controle van de factorisatie. Deze controle vervangt de eigen Python-oplossing niet.

Resultaat

De grootste priemfactor van 600851475143 is 6857.

Uitvoeringstijd: ongeveer 0,00012068 seconden.

Besluit

Proefdeling is voor deze opgave eenvoudig, inzichtelijk en snel genoeg. Door gevonden factoren meteen volledig uit te delen, blijft het aantal benodigde controles beperkt en vinden we zonder externe bibliotheken het juiste antwoord.

VWO 2026 finale vraag 4

Geplaatst op 6 augustus 2026 door admin

Een punt beweegt over een aangeschreven cirkel van een gelijkzijdige driehoek. Hoe verhouden zijn loodrechte afstanden tot de drie zijrechten zich? Met geschikte coördinaten en een parametrisatie van de cirkel wordt de meetkundige ongelijkheid een scherpe cosinusschatting.

Infobox

Onderwerpen: Meetkunde, analytische meetkunde, goniometrie
Probleemoplossingstechnieken: Normaliseren, coördinaten invoeren, parametriseren, afstanden tot rechten vergelijken
Moeilijkheid: Moeilijk
Competitie: Vlaamse Wiskunde Olympiade
Jaar: 2026
Opgavenummer: 4

Opgave

In de figuur zie je een gelijkzijdige driehoek $\triangle ABC$ en de cirkel met middelpunt buiten $\triangle ABC$ die raakt aan het lijnstuk $[BC]$ en aan de rechten $AB$ en $AC$ . Punt $P$ ligt op de cirkel en de punten $L$ , $M$ en $N$ zijn de loodrechte projecties van $P$ op respectievelijk de rechten $BC$ , $AC$ en $AB$ .

Bewijs dat

$3|PL|\leq 2|PM|+2|PN|.$

Figuur 1

Figuur 1.

Eerste idee

De cirkel is de $A$ -aangeschreven cirkel van de gelijkzijdige driehoek. Schaal de zijde naar $1$ , bepaal het uitmiddelpunt en parametriseer $P$ met een hoek $\theta$ . De afstanden tot de drie zijrechten worden dan lineaire uitdrukkingen in $\cos\theta$ en $\sin\theta$ . Na invullen is het verschil tussen rechter- en linkerkant een positieve straal maal $1-\cos(\theta-\pi/6)$ .

Uitwerking

Stap 1: normalisatie en coördinaten

We gebruiken eerst dat gelijkvormigheid alle lengtes met dezelfde positieve factor vermenigvuldigt. Daardoor blijft de te bewijzen homogene ongelijkheid onveranderd. We mogen dus veronderstellen dat de zijde van de gelijkzijdige driehoek lengte $1$ heeft.

Kies een assenstelsel met

$A=(0,0),\qquad B=(1,0),\qquad C=\left(\frac12,\frac{\sqrt3}{2}\right).$

Omdat alle hoeken van een gelijkzijdige driehoek $60^\circ$ zijn, hebben de drie zijrechten de vergelijkingen

$AB:\ y=0,$

$AC:\ \frac{\sqrt3}{2}x-\frac12y=0,$

$BC:\ \frac{\sqrt3}{2}x+\frac12y=\frac{\sqrt3}{2}.$

Stap 2: middelpunt en straal

We gebruiken het kenmerk van de bissectrices: een punt dat gelijke afstanden tot twee snijdende rechten heeft, ligt op een van hun bissectrices. Het middelpunt van een cirkel die aan de drie zijrechten raakt, ligt daarom op drie geschikte bissectrices.

De incenter valt af omdat het middelpunt buiten de driehoek ligt. Bij het $B$ -uitmiddelpunt en het $C$ -uitmiddelpunt ligt het loodrechte voetpunt op de rechte $BC$ respectievelijk voorbij $C$ en voorbij $B$ . Omdat het raakpunt hier op het lijnstuk $[BC]$ ligt, is $O$ dus het $A$ -uitmiddelpunt. De interne bissectrice bij $A$ heeft vergelijking

$y=\frac{x}{\sqrt3},$

en de externe bissectrice bij $B$ die het $A$ -uitmiddelpunt bevat, heeft vergelijking

$y=\sqrt3(x-1).$

Hun snijpunt is

$O=\left(\frac32,\frac{\sqrt3}{2}\right).$

We gebruiken vervolgens de stelling dat de straal naar een raakpunt loodrecht op de raaklijn staat. De loodrechte afstand van $O$ tot elk van de drie raaklijnen is dus de straal $r$ . Uit de afstand van $O$ tot $AB$ volgt

$r=\frac{\sqrt3}{2}.$

Stap 3: parametrisatie van $P$

Figuur 2. Hulpconstructie voor het bewijs.

Figuur 2. Hulpconstructie voor het bewijs.

Omdat $P$ op de cirkel met middelpunt $O$ en straal $r$ ligt, bestaat er een reëel getal $\theta$ waarvoor

$P=O+r(\cos\theta,\sin\theta).$

We gebruiken nu de afstandformule met een eenheidsnormaal. Voor een rechte met vergelijking $\mathbf n\cdot X=c$ , waarbij $\mathbf n$ een eenheidsvector is, is de loodrechte afstand van $X$ tot de rechte gelijk aan $|\mathbf n\cdot X-c|$ .

Kies de naar $O$ gerichte eenheidsnormalen

$\mathbf n_{AB}=(0,1),\qquad \mathbf n_{AC}=\left(\frac{\sqrt3}{2},-\frac12\right),\qquad \mathbf n_{BC}=\left(\frac{\sqrt3}{2},\frac12\right).$

Het middelpunt $O$ ligt bij elk van de drie rechten op afstand $r$ aan de gekozen positieve zijde. De cirkel met straal $r$ ligt dus volledig in de bijbehorende gesloten halfvlakken. Daarom zijn de volgende gesigneerde uitdrukkingen voor elk punt $P$ op de cirkel niet-negatief en zijn ze precies de loodrechte afstanden.

Voor de rechte $AB$ krijgen we

$|PN|=r(1+\sin\theta).$

Voor de rechte $AC$ krijgen we

$|PM|=r\left(1+\frac{\sqrt3}{2}\cos\theta-\frac12\sin\theta\right).$

Voor de rechte $BC$ krijgen we

$|PL|=r\left(1+\frac{\sqrt3}{2}\cos\theta+\frac12\sin\theta\right).$

Stap 4: de ongelijkheid

We trekken de linkerkant van de gewenste ongelijkheid af van de rechterkant en vullen de drie afstandsformules in:

$\begin{aligned} 2|PM|+2|PN|-3|PL| &=r\left(1-\frac{\sqrt3}{2}\cos\theta-\frac12\sin\theta\right)\\ &=r\left(1-\cos\left(\theta-\frac{\pi}{6}\right)\right). \end{aligned}$

In de tweede gelijkheid gebruiken we de verschilformule voor de cosinus. Voor elke reële hoek $\varphi$ geldt $\cos\varphi\leq 1$ , en bovendien is $r>0$ . Bijgevolg is

$2|PM|+2|PN|-3|PL|\geq 0.$

Dus

$\boxed{3|PL|\leq 2|PM|+2|PN|}.$

Probleemoplossingstechnieken

Normaliseren: De zijde wordt op $1$ geschaald omdat de ongelijkheid homogeen is in lengtes.
Coördinaten invoeren: Standaardcoördinaten bepalen het uitmiddelpunt en de drie zijrechten exact.
Parametriseren: Het punt $P$ wordt met één hoekparameter op de cirkel beschreven.
Afstanden tot rechten vergelijken: Eenheidsnormalen zetten de drie projectielengtes om in lineaire uitdrukkingen in $\cos\theta$ en $\sin\theta$ .

Bron

Officiële wedstrijdbundel: https://www.vwo.be/vwo/wp-content/uploads/2026/04/VWO-finale-2026.pdf

VWO 2026 finale vraag 3

Geplaatst op 6 augustus 2026 door admin

Hoe vind je alle positieve gehele oplossingen van een vergelijking waarin de onbekenden zowel in de grondtallen als in de exponenten voorkomen? Een ontbinding via de grootste gemene deler legt de verborgen structuur bloot en leidt tot een volledige familie oplossingen.

Infobox

Onderwerpen: Algebra, getaltheorie
Probleemoplossingstechnieken: Substitutie, ggd-ontbinding, werk achteruit, speciale gevallen
Moeilijkheid: Moeilijk
Competitie: Vlaamse Wiskunde Olympiade
Jaar: 2026
Opgavenummer: 3

Opgave

Bepaal alle paren $(a,b)$ van strikt positieve gehele getallen waarvoor geldt

$(a+b)^a=b^{a+b}.$

Eerste idee

Schrijf $a=du$ en $b=dv$ , waarbij $d=\gcd(a,b)$ en $\gcd(u,v)=1$ . Na vereenvoudiging ontstaat een vergelijking waarin $u+v$ en $v$ naast elkaar staan. Omdat die twee getallen onderling ondeelbaar zijn, kan $v$ geen priemfactor hebben. Dat bepaalt eerst $v$ , waarna de volledige familie oplossingen rechtstreeks volgt.

Uitwerking

We schrijven de vergelijking als

$(a+b)^a=b^{a+b}.$

Neem nu de grootste gemene deler van $a$ en $b$ . Schrijf

$a=du,\qquad b=dv,$

waarbij

$d=\gcd(a,b),\qquad \gcd(u,v)=1.$

Dan is

$(d(u+v))^{du}=(dv)^{d(u+v)}.$

We nemen de $d$ -de wortel. Omdat beide zijden positieve gehele getallen zijn, volgt

$(d(u+v))^u=(dv)^{u+v}.$

Na verdelen door $d^u$ krijgen we

(1) $(u+v)^u=d^v v^{u+v}.$

Nu gebruiken we dat $\gcd(u,v)=1$ . Dan is ook

$\gcd(u+v,v)=1.$

Kies een priemgetal $p$ dat $v$ deelt. Omdat $p\nmid u+v$ , heeft de linkerkant van (1) geen factor $p$ . Aan de rechterkant verschijnt die factor echter wel via $v^{u+v}$ , en dus heeft de rechterkant een positieve $p$ -macht. Dat is onmogelijk.

Daarom kan er geen enkel priemgetal $v$ delen. Dus

$v=1.$

We hebben dus

$b=d,\qquad a=du.$

Invullen in (1) geeft

$(u+1)^u=d.$

Dus

$b=d=(u+1)^u,\qquad a=du=u(u+1)^u.$

Dit levert voor elke positieve gehele waarde van $u$ een oplossing.

We controleren nu dat deze oplossingen werkelijk werken. Neem

$a=u(u+1)^u,\qquad b=(u+1)^u.$

Dan is

$a+b=u(u+1)^u+(u+1)^u=(u+1)^{u+1}.$

Daarom geldt

$(a+b)^a=((u+1)^{u+1})^{u(u+1)^u}=(u+1)^{u(u+1)^{u+1}}.$

Aan de andere kant is

$b^{a+b}=\bigl((u+1)^u\bigr)^{(u+1)^{u+1}}=(u+1)^{u(u+1)^{u+1}}.$

Dus

$(a+b)^a=b^{a+b}.$

Alle oplossingen zijn dus precies de paren

$\boxed{(a,b)=\bigl(u(u+1)^u,(u+1)^u\bigr)\quad\text{met }u\in\mathbb{Z}_{>0}.}$

In het bijzonder krijgen we bijvoorbeeld

$(u=1)\to (a,b)=(2,2),$

$(u=2)\to (a,b)=(18,9).$

Probleemoplossingstechnieken

Ggd-ontbinding: Schrijf $a=du$ en $b=dv$ om de gemeenschappelijke factor af te zonderen.
Substitutie: De nieuwe variabelen $d$ , $u$ en $v$ maken de machtsvergelijking hanteerbaar.
Werk achteruit: Vul de gevonden familie opnieuw in om te controleren dat elk paar werkelijk een oplossing is.
Speciale gevallen: Het geval $a=b$ levert snel de eerste oplossing $(2,2)$ op.