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.

Project Euler 002 – Even Fibonacci-getallen

Geplaatst op 29 juli 2026 door admin

Probleemstelling

De Fibonacci-reeks start met 1, 1, 2, 3, 5, 8, 13, …

Elke term na de eerste twee wordt gevormd door de som van de twee voorgaande termen.

Bepaal de som van alle even Fibonacci-termen die kleiner zijn dan 4.000.000.

Eerste analyse

Voor deze opgave is een eenvoudige iteratieve aanpak zeer geschikt. We genereren Fibonacci-getallen in een lus en controleren voor elk getal of het even is. Omdat de reeks snel groeit, zijn maar weinig termen nodig om de limiet te overschrijden.

Gekozen programmeeraanpak

We houden twee opeenvolgende Fibonacci-getallen bij en berekenen steeds de volgende term. Als de huidige term even is, voegen we die toe aan de som.

Deze aanpak is helder, compact en volledig voldoende voor deze opgave.

Algoritme

Initialiseer twee Fibonacci-termen: 1 en 2.
Herhaal zolang de huidige term kleiner is dan 4.000.000.
Controleer of de huidige term even is.
Voeg de even term toe aan de som.
Bereken de volgende Fibonacci-term.
Druk de som en de uitvoeringstijd af.

Python-programma

import time


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


# Bereken de som van alle even Fibonacci-termen kleiner dan 4.000.000
limiet = 4_000_000
vorige = 1
huidige = 2
som = 0

while huidige < limiet:
    if huidige % 2 == 0:
        som += huidige

    vorige, huidige = huidige, vorige + huidige


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


# Toon het resultaat
print(f"De gevraagde som is: {som}")
print(f"Uitvoeringstijd: {uitvoeringstijd:.8f} seconden")

Wiskundige oplossing

We gebruiken de conventie $F_1 = F_2 = 1$ .

De Fibonacci-reeks begint dus als

$1, 1, 2, 3, 5, 8, 13, 21, 34, \dots$

Pariteit van Fibonacci-getallen

We schrijven de pariteit van de termen op:

$\text{oneven},\;\text{oneven},\;\text{even},\;\text{oneven},\;\text{oneven},\;\text{even},\;\dots$

De pariteit is dus periodiek met periode $3$ . Het patroon herhaalt zich steeds volgens

$\text{oneven}, \text{oneven}, \text{even}.$

Daaruit volgt direct dat

$F_n \text{ is even } \Longleftrightarrow 3 \mid n.$

De even Fibonacci-getallen zijn dus precies

$F_3, F_6, F_9, \dots, F_{3m}.$

Bewijs van de identiteit $\sum_{k=1}^{n}F_k = F_{n+2}-1$

We bewijzen deze identiteit met inductie naar $n$ .

Voor $n=1$ geldt

$\sum_{k=1}^{1}F_k = F_1 = 1,$

en ook

$F_{1+2}-1 = F_3-1 = 2-1 = 1.$

Neem nu aan dat voor een zekere $n\geq 1$

$\sum_{k=1}^{n}F_k = F_{n+2}-1.$

Dan volgt

$\sum_{k=1}^{n+1}F_k = \left(\sum_{k=1}^{n}F_k\right) + F_{n+1} = (F_{n+2}-1) + F_{n+1}.$

Omdat $F_{n+3}=F_{n+2}+F_{n+1}$ , krijgen we

$\sum_{k=1}^{n+1}F_k = F_{n+3}-1.$

Dus is de formule geldig voor $n+1$ . Daarmee is de identiteit bewezen.

Bewijs van de identiteit $\sum_{k=1}^{m}F_{3k} = \dfrac{F_{3m+2}-1}{2}$

We bewijzen ook deze formule met inductie naar $m$ .

Voor $m=1$ geldt

$\sum_{k=1}^{1}F_{3k} = F_3 = 2,$

terwijl

$\frac{F_{3\cdot 1+2}-1}{2} = \frac{F_5-1}{2} = \frac{5-1}{2} = 2.$

Neem nu aan dat voor een zekere $m\geq 1$

$\sum_{k=1}^{m}F_{3k} = \frac{F_{3m+2}-1}{2}.$

Dan volgt

$\sum_{k=1}^{m+1}F_{3k} = \left(\sum_{k=1}^{m}F_{3k}\right) + F_{3m+3} = \frac{F_{3m+2}-1}{2} + F_{3m+3}.$

Na vereenvoudiging verkrijg je

$\sum_{k=1}^{m+1}F_{3k} = \frac{F_{3m+5}-1}{2},$

wat precies de gewenste vorm is voor $m+1$ . De identiteit is dus bewezen.

Relatie met de totale som

Uit de vorige identiteit volgt nu direct dat

$\sum_{k=1}^{m}F_{3k} = \frac12\sum_{k=1}^{3m}F_k.$

Toepassing op Euler 002

We weten dat

$F_{33} = 3\,524\,578 < 4\,000\,000 < F_{34}.$

Dus is het grootste even Fibonacci-getal onder de limiet gelijk aan $F_{33}$ , en daarmee is $m=11$ .

Nu berekenen we

$\sum_{k=1}^{11}F_{3k} = \frac{F_{35}-1}{2} = \frac{9\,227\,465-1}{2} = 4\,613\,732.$

De gevraagde som is dus

$\boxed{4\,613\,732}.$

Wiskundige opmerking

Deze oplossing vereist slechts een constante hoeveelheid werk. De pariteitsregel, de inductie en de compacte somformule leveren het antwoord direct op, zonder dat de Fibonacci-getallen één voor één moeten worden gegenereerd. De programmeeroplossing doet dat wel, maar is in dat opzicht meer rekenintensief.

Resultaat

De gevraagde som is 4613732.

Uitvoeringstijd: ongeveer 0,00002408 seconden.

Besluit

Deze aanpak is eenvoudig, begrijpelijk en levert direct het juiste antwoord.

Project Euler 001 – Veelvouden van 3 en 5

Geplaatst op 28 juli 2026 door admin

Probleemstelling

Wanneer alle natuurlijke getallen kleiner dan 10 die een veelvoud zijn van 3 of 5 worden opgeteld, bekomt men

3 + 5 + 6 + 9 = 23.

Bepaal de som van alle natuurlijke getallen kleiner dan 1000 die een veelvoud zijn van 3 of 5.

Eerste analyse

Voor deze eerste Euler-opgave is een brute-force aanpak voldoende en het meest begrijpelijk. We lopen alle natuurlijke getallen van 1 tot en met 999 door en controleren voor elk getal of het een veelvoud is van 3 of 5. Omdat er slechts 999 waarden onderzocht moeten worden, is deze aanpak snel genoeg en zeer geschikt voor een eerste opgave.

Programmeeraanpak

We gebruiken een eenvoudige lus die alle getallen van 1 tot en met 999 doorloopt. Voor elk getal controleren we of het deelbaar is door 3 of door 5. Indien dit het geval is, voegen we het getal toe aan de som.

Deze aanpak is direct, leesbaar en correct.

Algoritme

Initialiseer een variabele som met waarde 0.
Loop over alle getallen van 1 tot en met 999.
Controleer voor elk getal of het deelbaar is door 3 of door 5.
Voeg het getal toe aan som als één van beide voorwaarden waar is.
Druk het eindantwoord en de uitvoeringstijd af.

Python-programma

import time


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


# Bereken de som van alle veelvouden van 3 of 5 kleiner dan 1000
som = 0

for getal in range(1, 1000):
    if getal % 3 == 0 or getal % 5 == 0:
        som += getal


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


# Toon het resultaat
print(f"De gevraagde som is: {som}")
print(f"Uitvoeringstijd: {uitvoeringstijd:.8f} seconden")

Oplossing

We onderzoeken alle natuurlijke getallen kleiner dan 1000. Voor elk getal controleren we of het een veelvoud is van 3 of 5. Als dat zo is, tellen we het getal mee in de som. Daarna drukken we de eindsom af.

Deze aanpak levert het juiste antwoord, omdat alle relevante getallen precies één keer worden gecontroleerd.

Wiskundige oplossing

Een compacte wiskundige oplossing gebruikt de somformule van een rekenkundige reeks.

We berekenen apart:

de som van alle veelvouden van 3;
de som van alle veelvouden van 5;
en trekken vervolgens de dubbeltellingen van de veelvouden van 15 weer af.

Dus:

$3(1+2+\cdots+333) + 5(1+2+\cdots+199) - 15(1+2+\cdots+66)$

Met

$1+2+\cdots+n=\frac{n(n+1)}{2}$

volgt:

$3\cdot\frac{333\cdot 334}{2} + 5\cdot\frac{199\cdot 200}{2} - 15\cdot\frac{66\cdot 67}{2} = 233168$

Daarom is het antwoord:

$\boxed{233168}$

Eindantwoord

De gevraagde som is 233168.

Uitvoeringstijd

De uitvoeringstijd van het Python-programma bedraagt 0.00010779 seconden.

Besluit

Deze aanpak is eenvoudig, helder en volledig geschikt voor deze eerste Euler-opgave. De brute-force methode levert direct het juiste resultaat en is tegelijk een uitstekende introductie tot programmeren en probleemoplossen.