Project Euler 009 – Een bijzonder pythagorees drietal

Probleemstelling

Een pythagorees drietal bestaat uit drie positieve gehele getallen $a<b<c$ waarvoor

$a^2+b^2=c^2.$

Zo vormen 3, 4 en 5 een voorbeeld, want $3^2+4^2=9+16=25=5^2$ .

Er is precies één dergelijk drietal met $a+b+c=1000$ . Bepaal het product $abc$ .

Eerste analyse

We kunnen mogelijke waarden van $a$ , $b$ en $c$ proberen, maar drie lussen doen veel overbodig werk. Zodra $a$ en $b$ gekozen zijn, ligt $c=1000-a-b$ vast.

Omdat $a<b<c$ , geldt $3a<1000$ . We hoeven dus alleen $a=1,\ldots,333$ te onderzoeken. Voor $b$ geldt

$a+1\le b\le\left\lfloor\frac{999-a}{2}\right\rfloor,$

want $b<c$ betekent $2b<1000-a$ . Zo blijven 82.834 kandidaatparen over: een kleine zoekruimte voor Python.

Gekozen programmeeraanpak en algoritme

We gebruiken twee lussen en rekenen uitsluitend met gehele getallen.

Kies achtereenvolgens waarden van $a$ en $b$ met twee lussen.
Bereken $c=1000-a-b$ en controleer $a^2+b^2=c^2$ .
Geef met return het eerste gevonden drietal terug.
Toon het drietal, het product en de uitvoeringstijd.

Deze compacte versie stopt bij de eerste oplossing. Ze controleert de gevonden tripel, maar bewijst niet de uniciteit. De opgave vermeldt dat de oplossing uniek is.

Voor een algemene som $S$ heeft deze aanpak tijdscomplexiteit $O(S^2)$ en extra geheugencomplexiteit $O(1)$ . Door algebraïsch $b=S(S-2a)/(2(S-a))$ af te leiden kan een programma met één lus worden gemaakt. De twee lussen houden de programmeercontrole eenvoudig en onafhankelijk van de parameterformule.

Python-programma

Het programma werkt zelfstandig met Python 3. // betekent gehele deling met afronding naar beneden. De eindgrens van range is niet inbegrepen. Deze compacte grenzen volstaan voor het gezochte drietal bij som 1000, maar kunnen voor andere sommen grensgevallen overslaan. Met return verlaat de functie beide lussen zodra een oplossing gevonden is.

from time import perf_counter


def zoek_tripel(som):
    for a in range(1, som // 3):
        for b in range(a + 1, (som - a) // 2):
            c = som - a - b
            if a**2 + b**2 == c**2:
                return a, b, c


start = perf_counter()
a, b, c = zoek_tripel(1000)
print(a, b, c)
print("Product:", a * b * c)
print("Tijd:", perf_counter() - start)

Wiskundige oplossing

De formule voor een pythagorees drietal

Voor gehele getallen $m>n>0$ gebruiken we het drietal

$(m^2-n^2,\;2mn,\;m^2+n^2).$

Dit voldoet aan de stelling van Pythagoras, want

$\begin{aligned} (m^2-n^2)^2+(2mn)^2 &=m^4-2m^2n^2+n^4+4m^2n^2\\ &=m^4+2m^2n^2+n^4\\ &=(m^2+n^2)^2. \end{aligned}$

Alle drie de getallen zijn positief. Bovendien is $m^2+n^2$ groter dan elk van de twee andere: de verschillen zijn $2n^2>0$ en $(m-n)^2>0$ . De twee rechthoekszijden moeten eventueel nog van plaats wisselen om $a<b$ te verkrijgen.

De somvoorwaarde gebruiken

De som van de drie uitdrukkingen is

$(m^2-n^2)+2mn+(m^2+n^2)=2m(m+n).$

We zoeken dus gehele getallen $m>n>0$ met

$2m(m+n)=1000, \qquad m(m+n)=500.$

Hieruit volgt dat $m$ een deler van 500 is en dat

$n=\frac{500}{m}-m.$

Uit $0<n<m$ volgt $m<m+n<2m$ . Vermenigvuldigen met $m>0$ geeft

$m^2<500<2m^2, \qquad \sqrt{250}<m<\sqrt{500}.$

Daarom komt alleen $m\in\{16,17,18,19,20,21,22\}$ in aanmerking. Omdat $500=2^2\cdot5^3$ , is 20 de enige deler van 500 in dat interval. Dus

$m=20,\qquad n=\frac{500}{20}-20=5.$

Het drietal en het product

Invullen levert

$m^2-n^2=400-25=375,\qquad 2mn=200,\qquad m^2+n^2=425.$

Na ordenen krijgen we

$(a,b,c)=(200,375,425).$

We controleren rechtstreeks:

$200+375+425=1000,$

$200^2+375^2=40000+140625=180625=425^2.$

Het gevraagde product is bijgevolg

$\boxed{200\cdot375\cdot425=31875000}.$

Wiskundige verdieping: primitieve drietallen en uniciteit

Een drietal heet primitief wanneer zijn drie getallen geen gemeenschappelijke deler groter dan 1 hebben. Het gevonden drietal is niet primitief:

$(200,375,425)=25(8,15,17).$

De primitieve tripel ontstaat met $m=4$ en $n=1$ ; onze keuze $m=20$ , $n=5$ vermenigvuldigt beide parameters met 5 en daardoor alle zijden met $5^2=25$ .

Voor het vormen van een geldig drietal hoeven $m$ en $n$ dus niet onderling ondeelbaar te zijn. Voor een primitief drietal vraagt men wel dat $m$ en $n$ onderling ondeelbaar zijn en een verschillende pariteit hebben.

De ongeschaalde formule alleen beschrijft niet alle gehele pythagorese drietallen. Voor een volledige parametrisering gebruikt men ook een positieve gehele schaalfactor $k$ :

$k(m^2-n^2,\;2mn,\;m^2+n^2).$

Het vinden van één parameterpaar in onze ongeschaalde formule is daarom op zichzelf geen volledig uniciteitsbewijs. Het compacte Python-programma vindt onafhankelijk hetzelfde drietal, maar stopt bij de eerste oplossing. Het levert daarom geen afzonderlijk uniciteitsbewijs.

Controle met Python en resultaat

Een uitvoering van het compacte programma gaf:

200 375 425
Product: 31875000
Tijd: 0.009028022001075442

Het antwoord is 31875000. De gemeten uitvoeringstijd was 0,009028022001075442 seconden. De meting omvat de zoekopdracht en het afdrukken van het drietal en het product. De tijd kan verschillen naargelang de computer, Python-versie en systeembelasting.

Besluit

De formule $(m^2-n^2,2mn,m^2+n^2)$ herleidt de somvoorwaarde tot $m(m+n)=500$ . Met $m=20$ en $n=5$ vinden we na ordenen $(200,375,425)$ . Het compacte Python-programma vindt onafhankelijk hetzelfde drietal. Het product bedraagt 31875000.