Tag archieven: problem solving

Project Euler 005 – Kleinste veelvoud

Geplaatst op door

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

  1. Maak een functie die met het algoritme van Euclides de grootste gemene deler berekent.
  2. Stel het lopende kleinste gemene veelvoud gelijk aan 1.
  3. Doorloop de getallen van 2 tot en met 20.
  4. Bereken telkens het nieuwe kgv met de ggd-formule.
  5. 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.

Nootje 72

Geplaatst op door

Voor welke gehele waarde van k heeft de veelterm P(x)=x^3-87x^2+181x+k  drie gehele nulwaarden?

Antwoord

  • Noem de drie nulwaarden a,b en c.
  • Dan moet a+b+c=87. Omdat 87 oneven is moeten van a,b en c  er twee even en één oneven zijn ofwel moeten ze alle drie oneven zijn.
  • Verder moet ab+ac+bc=181. Als er twee van de drie nulwaarden even zijn is het linkerlid zeker even en vermits het rechterlid oneven is, is dit onmogelijk.
  • Bijgevolg zijn de drie nulwaarden alle drie oneven. Stel a=1+2d,b=1+2e en c=1+2f.
  • Dan moet (1+2d)(1+2e)+(1+2e)(1+2f)+(1+2f)(1+2d)=181. Uitgewerkt geeft dit:

        \[3+4(d+e+f+de+df+ef)=181\]

  • Dus: 4(d+e+f+de+df+ef)=178. Dit is onmogelijk, want het linkerlid is een viervoud en het rechterlid niet.
  • Er is dus geen gehele waarde van k te vinden waarvoor de gegeven veelterm drie gehele nulwaarden heeft.

 

 

Nootje 70

Geplaatst op door

Bepaal de som A van alle natuurlijke getallen tussen \sqrt[3]{2026} en \sqrt{2026}.

Antwoord

  • Omdat 12^3=1728 en 13^3=2197 weten we dat 12<\sqrt[3]{2026}<13}.
  • Omdat 45^2=2025 en 46^2=2116 weten we dat 45<\sqrt{2026}<46.
  • Dan is A=13+14+\cdots+45.
  • We kunnen deze som berekenen door de formule te gebruiken van de som van de termen van een rekenkundige rij. Deze som is het product van het gemiddelde van de eerste en laatste term met het aantal termen.
  • Bijgevolg is

        \[A=\frac{13+45}{2}\times 33=957\]