Project Euler 005 – Kleinste veelvoud

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.