Project Euler 006 – Verschil tussen kwadratensommen

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

Stel beide sommen gelijk aan 0.
Doorloop de getallen van 1 tot en met 100.
Tel ieder getal op bij de gewone som.
Tel ieder kwadraat op bij de som van de kwadraten.
Kwadrateer de gewone som.
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.