Tag archieven: python

Project Euler 006 – Verschil tussen kwadratensommen

Geplaatst op door

Probleemstelling

De som van de kwadraten van de eerste tien natuurlijke getallen is

    \[1^2+2^2+\cdots+10^2=385.\]

Het kwadraat van de som van de eerste tien natuurlijke getallen is

    \[(1+2+\cdots+10)^2=55^2=3025.\]

Het verschil is dus 3025-385=2640.

Bepaal het verschil tussen het kwadraat van de som en de som van de kwadraten van de eerste honderd natuurlijke getallen.

Eerste analyse

We kunnen de twee gevraagde waarden rechtstreeks berekenen. Tijdens één lus houden we zowel de som van de getallen als de som van hun kwadraten bij. Omdat slechts honderd getallen worden verwerkt, is deze aanpak bijzonder snel.

Daarnaast bestaat een elegante wiskundige oplossing met de formules voor de som van de eerste n natuurlijke getallen en de som van de eerste n kwadraten.

Gekozen programmeeraanpak

Het Python-programma gebruikt één for-lus die de getallen van 1 tot en met 100 doorloopt. Voor elk getal werken we twee totalen bij:

  • som bevat de gewone som;
  • som_van_kwadraten bevat de som van de afzonderlijke kwadraten.

Na de lus berekenen we som**2, het kwadraat van de som. Daarvan trekken we de som van de kwadraten af.

Algoritme

  1. Stel beide sommen gelijk aan 0.
  2. Doorloop de getallen van 1 tot en met 100.
  3. Tel ieder getal op bij de gewone som.
  4. Tel ieder kwadraat op bij de som van de kwadraten.
  5. Kwadrateer de gewone som.
  6. Bereken het verschil en druk het resultaat af.

Python-programma

import time


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


# Bereken de som en de som van de kwadraten
som = 0
som_van_kwadraten = 0

for getal in range(1, 101):
    som += getal
    som_van_kwadraten += getal**2


# Bereken het gevraagde verschil
kwadraat_van_som = som**2
verschil = kwadraat_van_som - som_van_kwadraten


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


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

Voor een algemene bovengrens n heeft deze lus tijdscomplexiteit O(n). Het programma gebruikt slechts een vast aantal variabelen en heeft daarom geheugencomplexiteit O(1).

Wiskundige oplossing

De som van de eerste n natuurlijke getallen wordt gegeven door

    \[1+2+\cdots+n=\frac{n(n+1)}{2}.\]

Voor n=100 krijgen we

    \[1+2+\cdots+100 =\frac{100\cdot101}{2} =5050.\]

Het kwadraat van de som is bijgevolg

    \[5050^2=25\,502\,500.\]

Voor de som van de eerste n kwadraten gebruiken we

    \[1^2+2^2+\cdots+n^2 =\frac{n(n+1)(2n+1)}{6}.\]

Invullen van n=100 geeft

    \[1^2+2^2+\cdots+100^2 =\frac{100\cdot101\cdot201}{6} =338\,350.\]

Het gevraagde verschil is dus

    \[25\,502\,500-338\,350 =25\,164\,150.\]

Daarom is het antwoord

    \[\boxed{25164150}.\]

Resultaat

Het verschil tussen het kwadraat van de som en de som van de kwadraten is 25164150.

Uitvoeringstijd: 0,00006433 seconden.

Besluit

De programmeeroplossing met één lus is duidelijk en snel. De twee somformules bieden daarnaast een elegante constante-tijdoplossing en bevestigen hetzelfde resultaat: 25164150.

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.

Project Euler 004 – Grootste palindroomproduct

Geplaatst op door

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

We maken eerst een afzonderlijke, algemene functie is_palindroom(uitdrukking). Ze zet haar argument indien nodig om naar tekst en vergelijkt die tekst met haar omgekeerde. De functie is dus niet speciaal geschreven voor producten van driecijferige getallen.

Door de palindroomtest los te koppelen van de zoeklussen krijgt elk programmadeel één duidelijke taak. De functie kan afzonderlijk worden getest en hergebruikt, terwijl het hoofdalgoritme overzichtelijk blijft.

Daarna daalt de eerste factor van 999 tot 100. De tweede factor daalt telkens van 999 tot de eerste factor, zodat elk ongeordend factorpaar hoogstens eenmaal wordt onderzocht.

Alleen producten die groter zijn dan het tot dan toe gevonden maximum blijven interessant. Wanneer een product in de dalende binnenste lus niet meer groter is, mogen we die lus afbreken. Voor ieder nog interessant product gebruiken we is_palindroom(); bij een positief resultaat bewaren we het product en beide factoren.

De functie is_palindroom()

def is_palindroom(uitdrukking) -> bool:
    tekst = str(uitdrukking)
    return tekst == tekst[::-1]

str(uitdrukking) maakt een tekstvoorstelling van de ontvangen waarde. De uitdrukking tekst[::-1] levert dezelfde tekst in omgekeerde volgorde. Zijn beide teksten gelijk, dan geeft de functie True terug; anders geeft ze False terug. Zo werkt de functie bijvoorbeeld voor het getal 9009, maar ook voor een tekst zoals "lepel".

Algoritme

  1. Initialiseer het grootste palindroom met 0.
  2. Doorloop de eerste factor dalend van 999 tot en met 100.
  3. Doorloop de tweede factor dalend van 999 tot en met de eerste factor.
  4. Bereken het product.
  5. Breek de lus af wanneer geen groter product meer mogelijk is.
  6. Test het product met de algemene functie is_palindroom().
  7. Bewaar elk groter gevonden palindroom en zijn factoren.
  8. Druk het antwoord, de factoren en de uitvoeringstijd af.

Python-programma

import time


# Controleer of een uitdrukking een palindroom is
def is_palindroom(uitdrukking) -> bool:
    tekst = str(uitdrukking)
    return tekst == tekst[::-1]


# 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

        if is_palindroom(product):
            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")

Complexiteit en eenvoudige optimalisaties

Met n mogelijke driecijferige factoren onderzoeken de twee geneste lussen in het ongunstigste geval een kwadratisch aantal paren. De tijdscomplexiteit is daarom O(n^2) wanneer de cijferlengte vast is. De tekstvergelijking in is_palindroom() kost voor een getal met d cijfers O(d) tijd, zodat de algemene notatie O(n^2d) is. Het geheugengebruik blijft O(1).

De code vermijdt dubbele factorparen, doorloopt grote producten eerst en breekt een lus af zodra geen verbetering meer mogelijk is. Men zou ook de deelbaarheid van zescijferige palindromen door 11 in de lussen kunnen verwerken, maar die extra optimalisatie is voor deze kleine zoekruimte niet nodig.

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,00121165 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 002 – Even Fibonacci-getallen

Geplaatst op door

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

  1. Initialiseer twee Fibonacci-termen: 1 en 2.
  2. Herhaal zolang de huidige term kleiner is dan 4.000.000.
  3. Controleer of de huidige term even is.
  4. Voeg de even term toe aan de som.
  5. Bereken de volgende Fibonacci-term.
  6. 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 door

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

  1. Initialiseer een variabele som met waarde 0.
  2. Loop over alle getallen van 1 tot en met 999.
  3. Controleer voor elk getal of het deelbaar is door 3 of door 5.
  4. Voeg het getal toe aan som als één van beide voorwaarden waar is.
  5. 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.