In een machine zitten twee tandwielen. Eén tandwiel heeft 15 tanden en het andere 24 tanden. Op de plaatsen waar de tandwielen in elkaar grijpen, hebben we de tandwielen gemarkeerd met een rode lijn. Wat is het kleinste aantal omwentelingen van het eerste tandwiel dat de markeerlijnen van beide tandwielen terug naast elkaar zet?

Dit aantal omwentelingen kan berekend worden door het kleinste gemene veelvoud van het aantal tanden van beide tandwielen te delen door het aantal tanden van het eerste tandwiel. Dit is makkelijk in te zien als we voor elk tandwiel uitschrijven hoeveel tanden er bij elke volledige omwenteling voorbij het punt gekomen zijn waar de tandwielen in elkaar grijpen:

eerste tandwiel: 15, 30, 45, 60, 75, 90, 105, 120, 135, 150, 165, 180, 195, 210, 225, 240, 255, 270, 285, …
tweede tandwiel: 24, 48, 72, 96, 120, 144, 168, 192, 216, 240, 264, 288, 312, 336, 360, 384, 408, 432, 456, …

Als het eerste tandwiel acht volledige omwentelingen heeft gemaakt, dan zijn er in totaal 120 tanden voorbij het punt gekomen zijn waar de tandwielen in elkaar grijpen. Dit is hetzelfde aantal tanden dat voorbij dat punt gekomen is als het tweede tandwiel 5 volledige omwentelingen gemaakt heeft.

Voorbereiding

Bekijk de video over test-driven development¹ om te leren werken met doctests. Hierdoor zal je de laatste twee statements begrijpen in het skelet van de broncode dat wordt meegegeven met deze opgave.

Opgave

We hebben hieronder reeds het skelet opgemaakt voor de oplossing van deze opgave. Je taak bestaat erin om de functies ggd, kgv en omwentelingen te implementeren, zodat ze voor twee tandwielen met $$a$$ en $$b$$ tanden respectievelijk de volgende eigenschappen berekenen: i) de grootste gemene deler van het aantal tanden, ii) het kleinste gemene veelvoud van het aantal tanden en iii) het minimaal aantal omwentelingen van het eerste tandwiel waarna de tandwielen terug in de begintoestand staan. De grootste gemene deler is het grootste natuurlijke getal dat zowel een deler is van $$a$$ als van $$b$$. Het kleinste gemene veelvoud is het kleinste natuurlijke getal dat zowel een veelvoud is van $$a$$ als van $$b$$.

def ggd(a, b):
    
    """
    Berekent de grootste gemene deler van twee natuurlijke getallen a en b.

    >>> ggd(15, 24)
    3
    >>> ggd(252, 105)
    21
    """
    
    # berekening grootste gemene deler op basis van het algoritme van Euclides

def kgv(a, b):
    
    """
    Berekent het kleinste gemene veelvoud van twee natuurlijke getallen a en b.

    >>> kgv(15, 24)
    120
    >>> kgv(252, 105)
    1260
    """
    
    # berekening kleinste gemene veelvoud

def omwentelingen(a, b):
    
    """
    Berekent het kleinste aantal omwentelingen van een tandwiel met a tanden dat 
    tandwielen met a en b tanden terug in hun beginpositie brengt.

    >>> omwentelingen(15, 24)
    8
    >>> omwentelingen(252, 105)
    5
    """
    
    # berekening aantal omwentelingen

if __name__ == '__main__':
    import doctest
    doctest.testmod()

De fractions module uit de Python Standard Library² bevat een functie gcd die de grootste gemene deler van twee natuurlijke getallen teruggeeft. Voor deze opgave mag je de fractions module echter niet gebruiken, en is het de bedoeling dat je grootste gemene deler zelf berekent. Baseer je implementatie van de functie ggd op het algoritme van Euclides. Het algoritme start met een paar natuurlijke getallen, en vormt daarmee een nieuw paar dat bestaat uit het kleinste van de twee getallen, en het verschil tussen het grootste en het kleinste getal. Deze procedure herhaalt zich totdat het paar bestaat uit twee gelijke getallen. Dat getal is de grootste gemene deler van het oorspronkelijke paar natuurlijke getallen.

Het basisprincipe dat hierbij gehanteerd wordt, is dat de grootste gemene deler niet verandert als het kleinste van het grootste getal afgetrokken wordt. Zo is de grootste gemene deler van 252 en 105 ook de grootste gemene deler van 147 (= 252 - 105) en 105. Aangezien grootste getal verlaagd wordt, resulteert het herhaald uitvoeren van deze procedure in steeds kleinere getallen, zodat de herhaling vroeger of later zal stoppen wanneer de twee getallen gelijk zijn (als de procedure daarna nog een keer zou herhaald worden, dan zou één van beide getallen nul worden).

Het kleinste gemene veelvoud van twee natuurlijke getallen $$a$$ en $$b$$ kan bepaald worden als het product van beide getallen, gedeeld door hun grootste gemene deler.

Voorbeeld

>>> ggd(15, 24)
3
>>> ggd(252, 105)
21

>>> kgv(15, 24)
120
>>> kgv(252, 105)
1260

>>> omwentelingen(15, 24)
8
>>> omwentelingen(252, 105)
5