Project Euler 002 – Even Fibonacci-getallen

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.