(Primitieve) Pythagorese drietallen

[JTW]

Ik ben bezig een programma'tje te schrijven om primitieve pythagorese drietallen te vinden.
Een voorbeeld van een pythagorees drietal is 3,4,5 (zijden van een rechthoekige driehoek).

Een goede methode om alle pythagorese drietallen te vinden is:
men neemt een geheel reeël getal m, groter dan 0, bijvoorbeeld 2.
Daarna kies je nog een geheel reeël getal n, groter dan 0, maar kleiner dan het vorige getal.
Als de zijden van een rechthoekige driehoek a,b en c genoemd worden, met c als schuine zijde, is a=m2 - n2, b = 2mn, c = m2 + n2.

Met een eenvoudig loopje kun je dus alle Pythagorese drietallen vinden, door m steeds groter te maken en n te laten oplopen tot m-1.

Maar nu komt mijn vraag:
Hoe kun je nou met een simpel algoritme controleren of het primitieve drietallen zijn, zoals 3,4,5 en geen vermenigvuldigingen daarvan, zoals 6,8,10; 12,16,20; enz.
Om a,b,c te delen door alle getallen is nogal omslachtig en gaat natuurlijk erg veel tijd kosten op een Grafische Rekenmachine (TI83+ op mijn school) als m en n hoger dan 50 worden.

Bvd,
JTW

[Opi]

Je moet kijken wat de factoren van de afzonderlijke getallen zijn^*. Als alle getallen dezelfde factor hebben is het een vermenigvuldiging van een eerder gevonden drietal.

_{^*: kijken of het getal deelbaar is door de priemgetallen die kleiner zijn dan de wortel van het getal en een geheel getal opleveren.}

[ Voor 34% gewijzigd door Opi op 10-05-2004 09:47 ]

[Grijze Vos]

Je moet controleren of die 3 getallen geen gemene deler hebben. (6, 8 en 10 kun je alle drie delen door 2, bijvoorbeeld.)

[Verwijderd]

OM: Ik denk dat hij daar zelf ook wel achter was Echter, ken jij een efficient factorvindend algoritme?

@ TS: Ik heb geen idee in hoeverre een grafische rekenmachine programmeerbaar is, maar op een PC zou ik van elk gevonden drietal de verhouding tussen de grootste en de op 1 na grootste zijde berekenen. Deze verhouding is uniek voor een driehoek en dus zullen alleen driehoeken die dezelfde vorm hebben, dezelfde verhouding hebben. Deze verhouding zou ik vergelijken met de inhoud van een tabel waarin de verhoudingen van alle al gevonden drietallen staan. Staat de verhouding er al tussen, dan is het een veelvoud van een eerder drietal, is deze verhouding een nieuwe, dan heb je een nieuw drietal en komt de verhouding bij de andere te staan. Dit beperkt de hoeveelheid rekenwerk nogal, factorisering kost heel wat meer rekenwerk...

[ Voor 9% gewijzigd door Verwijderd op 10-05-2004 09:55 ]

[Opi]

Verwijderd schreef op 10 mei 2004 @ 09:53:
OM: Ik denk dat hij daar zelf ook wel achter was Echter, ken jij een efficient factorvindend algoritme?

Efficiënter dan het door mij geponeerde voorstel niet.

@ TS: Ik heb geen idee in hoeverre een grafische rekenmachine programmeerbaar is, maar op een PC zou ik van elk gevonden drietal de verhouding tussen de grootste en de op 1 na grootste zijde berekenen. Deze verhouding is uniek voor een driehoek en dus zullen alleen driehoeken die dezelfde vorm hebben, dezelfde verhouding hebben. Deze verhouding zou ik vergelijken met de inhoud van een tabel waarin de verhoudingen van alle al gevonden drietallen staan. Staat de verhouding er al tussen, dan is het een veelvoud van een eerder drietal, is deze verhouding een nieuwe, dan heb je een nieuw drietal en komt de verhouding bij de andere te staan. Dit beperkt de hoeveelheid rekenwerk nogal, factorisering kost heel wat meer rekenwerk...

Dit is idd een stuk sneller, je hebt alleen wel een behoorlijk geheugen nodig, lijkt me.

[Verwijderd]

Dit is idd een stuk sneller, je hebt alleen wel een behoorlijk geheugen nodig, lijkt me

Mja, dat zal wel meevallen denk ik... je hoeft maar 1 getal op te slaan per nieuw pythagoreisch drietal, dus zelfs als je er duizenden hebt zal er niet meer dan een paar KB aan geheugen benodigd zijn. En bovendien moet je hoe dan ook alle gevonden drietallen (nu ja, 2 van de drie) ergens opslaan, dus wat dat betreft heb je toch al veel geheugen nodig. Maar goed, ik heb geen idee hoeveel geheugen een grafische rekenmachine heeft, en of daar uberhaupt de mogelijkheid om met arrays te werken, in aanwezig is.

Overigens, nu ik erover nadenk, vraag ik me af of factorisatie niet toch sneller is dan vergelijken met een grote tabel. Voor grote getallen natuurlijk niet, voor de kleine getallen (m tot 50, dus de a, b en c tot ongeveer 5000) waar de TS in geinteresseerd is, misschien wel.

[JochemK]

paar kb, is op de TI-83 al snel veel, maar ik ben het idd met Captain Proton eens dat de manier met de tabellen wel de meest zinnige oplossing is voor dit geval.

[Grijze Vos]

Jij wilt dus floating point verhoudingen gaan opschrijven? Daar heeft dat ding weinig geheugen voor hoor, gaat best rap vol. 9 bytes per getal. Ik zou toch voor factoristatie gaan. Gemene delers zoeken etc.

[JTW]

Is er niet een aparte methode om alleen de primitieve drietallen te vinden, door niet met 'a=m2 - n2, b = 2mn, c = m2 + n2' te werken?

Het programmeren op de TI83+ biedt niet veel mogelijkheden(basic), daarom heb ik ook een HP49G, waarmee je praktisch alles kunt programmeren
Ondanks de tekortkomingen van de TI wil ik er wel dit programma mee maken, want anders snapt mijn leraar er helemaal niks van. (HP usr-rpl is niet zo makkelijk te begrijpen)

Het programma dat ik nu heb gemaakt op een TI83+ is als volgt:

code:

1->A                   //zet 1 in var A
0->B                   //zet 0 in var B  
Lbl A                  //Label A
If A>B                //Als A groter is dan B
Then
  ClrHome          //leeg scherm
  2AB->D            //bereken
  A*A-B*B->E
  A*A+B*B->F
    Output(1,6,A)    //output tonen
    Output(1,10,B)
    Output(1,1,D)
    Output(2,1,E)
    Output(3,1,F)
  B+1->B            //B groter maken
  Pause              //wachten op input om verder te gaan
Else                   //als A=B
A+1->A              //A groter maken
1->B                  //B wordt 1
End                   //EndIf
Goto A               //ga naar A

[ Voor 19% gewijzigd door JTW op 10-05-2004 13:14 ]

[Verwijderd]

Een zeer effectief algoritme om de grootste gemene deler (ggd) te vinden is het "Euclidisch Algoritme". Dit algoritme berekent de ggd van twee getallen a en b. Het derde getal c erbij betrekken is vervolgens simpel omdat gcd(a,b,c) = gcd(gcd(a,b),c). Controleren of een drietal een primitief Pythagoreisch drietal is, komt dan neer op bepalen of gcd(a,b,c,) = 1.

Zoeken met Google moet wel genoeg hits opleven over het Euclidisch Algoritme.

[Verwijderd]

Jij wilt dus floating point verhoudingen gaan opschrijven? Daar heeft dat ding weinig geheugen voor hoor, gaat best rap vol. 9 bytes per getal. Ik zou toch voor factoristatie gaan. Gemene delers zoeken etc.

Zoiets kan je natuurlijk een stuk efficienter aanpakken... Bijvoorbeeld door maar een paar decimalen op te slaan. Of, nog mooier, door alleen de lengte van de zijden op te slaan en het apparaat daaruit de deling te laten maken. Scheelt aanzienlijk in de hoeveelheid opslag die hij moet leveren, hoewel het qua rekentijd wel weer wat ongunstiger wordt. Maar goed, ik neem aan dat het erom gaat te bewijzen dat je algorithme voldoet, niet dat je rekenmachine het aankan voor grote getallen? Dan maakt het niet veel uit wat je kiest.

[ Voor 5% gewijzigd door Verwijderd op 10-05-2004 13:27 ]

[Verwijderd]

Volgens mij kun je ook wel gewoon de ggd van m en n berekenen als dat 1 is vermoed ik dat de ggd van a,b en c ook wel 1 wordt. Even denken...

Het is duidelijk dat als een getal p zowel m als n deelt, dat p dan ook een deler is van a, b en c (ga maar na). Nu nog de andere kant op...

Hmm, nee, dit blijkt toch niet te gelden. Tegenvoorbeeld:

(a,b,c) = (6,8,10) => (m,n) = (3,1)

Dus gcd(a,b,c) /= 1 terwijl (m,n) dat wel is...

Wat je dus moet doen, als je primitief PD wilt hebben, is beginnen met een m en n zodanig dat gcd(m,n) = 1 (men zegt dan dat m en n onderling priem zijn). Doe je dat niet, dan krijg je sowieso een drietal dat niet onderling priem is, maar gcd(m,n) = 1 biedt geen garantie dat je drietal primitief is. Je zult dus nog even moeten kijken wat gcd(a,b,c) is en dat gaat het best met het Euclidisch Algoritme.

[ Voor 94% gewijzigd door Verwijderd op 10-05-2004 14:23 ]

[Verwijderd]

Een klein zoektochtje op internet levert trouwens de precieze voorwaarde op voor m en n zodanig dat je een primitief PD krijgt.

Op deze dit staat te lezen dat:

A Pythagorean triple is primitive if and only if p and q are integers, q is odd, and (p, q) = 1.

waarbij m = p + q en n = p.

Oftewel in termen van m en n geformuleerd:

Een PD is primitief <=> gcd(m,n) = 1 en m-n oneven.

[ Voor 25% gewijzigd door Verwijderd op 10-05-2004 14:18 ]

[Verwijderd]

Verwijderd schreef op 10 mei 2004 @ 14:10:
Een klein zoektochtje op internet levert trouwens de precieze voorwaarde op voor m en n zodanig dat je een primitief PD krijgt.

Op deze dit staat te lezen dat:

[...]


waarbij m = p + q en n = p.

Oftewel in termen van m en n geformuleerd:

Een PD is primitief <=> gcd(m,n) = 1 en m-n oneven.

Bij de door jou genoemde link vind je bovendien een finder en een generator voor de TI86 voor Pythagorese triples. Nog sneller gaat het natuurlijk met de lijst die er ook staat.

[JTW]

Ok, het werkt inmiddels, maar op de TI83+ krijg ik bij m=48 en n=15 een memory problem.
Dat geeft niet, want het werkt perfect met een gcd(a,gcd(b,c)) erin verwerkt!
Het ligt alleen aan de brakke rekenmachine...

Bedankt!

[Sgrovert]

Kan het niet ook berekenen door als een 3 tal punten de goede verhoudingen hebben, door te testen of
A te delen is door een priemgetal, zo ja te testen of B en C er ook door te delen zijn. Op dit moment hebben ze dus een gemeenschappelijke deler, en is er geen nieuwe driehoek gevonden.

Zo nee te testen of A door een groter priemgetal te delen is. En bij dat kijken of B en C er ook door te delen zijn.
Hierbij zijn dus de volgende voorwaarden:
X is de kleindste van A, B, C

En het priemgetal wat ik kies is kleiner of gelijk aan X.

[Verwijderd]

JTW schreef op 10 mei 2004 @ 16:43:
Ok, het werkt inmiddels, maar op de TI83+ krijg ik bij m=48 en n=15 een memory problem.
Dat geeft niet, want het werkt perfect met een gcd(a,gcd(b,c)) erin verwerkt!
Het ligt alleen aan de brakke rekenmachine...

Bedankt!

Graag gedaan

[JTW]

Sgrovert schreef op 10 mei 2004 @ 16:55:
Kan het niet ook berekenen door als een 3 tal punten de goede verhoudingen hebben, door te testen of
A te delen is door een priemgetal, zo ja te testen of B en C er ook door te delen zijn. Op dit moment hebben ze dus een gemeenschappelijke deler, en is er geen nieuwe driehoek gevonden.

Zo nee te testen of A door een groter priemgetal te delen is. En bij dat kijken of B en C er ook door te delen zijn.
Hierbij zijn dus de volgende voorwaarden:
X is de kleindste van A, B, C

En het priemgetal wat ik kies is kleiner of gelijk aan X.

Het lastige hieraan is: hoe kom je zo snel aan een goed priemgetal, je kunt moeilijk alle priemgetallen tot X/2 gaan bereken, dat wordt een stuk langzamer...
Ook ontbreekt de functie op de GR om decimalen van getallen eenvoudig af te kappen van getallen. Dat maakt het controleren een stuk lastiger.

[Verwijderd]

sqrt((a+c)/2) in N (dus geheel)? zo ja, dan is dit gelijk aan m.
b/2m in N ? zo ja, dan is dit n.
Ga dan na wat de definitie is van primitieve drie tallen, en check of aan je eis is voldaan.
De eis is dus m > n > 0. (m,n)=1 en 2 deelt niet m-n.
m en n zijn trouwens niet zomaar reele getallen, want dan slaat het nergens op wat je bedoelt.
Het zijn natuurlijke getallen.

[ Voor 66% gewijzigd door Verwijderd op 10-05-2004 19:28 ]

[JTW]

Verwijderd schreef op 10 mei 2004 @ 19:21:
sqrt((a+c)/2) in N (dus geheel)? zo ja, dan is dit gelijk aan m.
b/2m in N ? zo ja, dan is dit n.
Ga dan na wat de definitie is van primitieve drie tallen, en check of aan je eis is voldaan.
De eis is dus m > n > 0. (m,n)=1 en 2 deelt niet m-n.
m en n zijn trouwens niet zomaar reele getallen, want dan slaat het nergens op wat je bedoelt.
Het zijn natuurlijke getallen.

Sorry, ik volg het eis stukje niet helemaal. Hoe kom je aan die eis?
En als je die eis hebt, kun je het eerste stukje van jou toch niet meer nodig, dan kun je toch gewoon het programma aanpassen?

[Verwijderd]

JTW schreef op 10 mei 2004 @ 21:17:
[...]

Sorry, ik volg het eis stukje niet helemaal. Hoe kom je aan die eis?
En als je die eis hebt, kun je het eerste stukje van jou toch niet meer nodig, dan kun je toch gewoon het programma aanpassen?

die "eis" is de definitie van het primitief zijn van een zo'n drietal
Het eerste stukje heb je wel degelijk nodig om uit een gegeven tripel de m en n weer te halen
en zo te checken of het primitief is.
Hierbij ga ik er van uit dat jouw vraag is: gegeven tripels waarvan de som van de kwadraten
van de eerste twee gelijk is aan het kwadraat van de derde. Ga dan na of dit tripel primitief is.

Als dit niet je vraag is, kan je hem dan duidelijker formuleren?

[ Voor 29% gewijzigd door Verwijderd op 10-05-2004 21:23 ]

[JTW]

Verwijderd schreef op 10 mei 2004 @ 21:21:
[...]


die "eis" is de definitie van het primitief zijn van een zo'n drietal
Het eerste stukje heb je wel degelijk nodig om uit een gegeven tripel de m en n weer te halen
en zo te checken of het primitief is.
Hierbij ga ik er van uit dat jouw vraag is: gegeven tripels waarvan de som van de kwadraten
van de eerste twee gelijk is aan het kwadraat van de derde. Ga dan na of dit tripel primitief is.

Als dit niet je vraag is, kan je hem dan duidelijker formuleren?

Dat zal ik doen:
In mijn programma ga ik uit van een m en n waarmee ik drietallen bereken, hoe kan ik uit deze gevormde drietallen op de beste(snelste, eenvoudigste) manier de primitieve drietallen overhouden?

Begrijp ik goed dat jij stelt dat je met
m > n > 0
(m,n)=1
2 deelt niet m-n
alleen PD'en over houdt?

(ik hoop dat dit duidelijk genoeg is )

[Verwijderd]

JTW schreef op 10 mei 2004 @ 21:51:
[...]


Dat zal ik doen:
In mijn programma ga ik uit van een m en n waarmee ik drietallen bereken, hoe kan ik uit deze gevormde drietallen op de beste(snelste, eenvoudigste) manier de primitieve drietallen overhouden?

Begrijp ik goed dat jij stelt dat je met
m > n > 0
(m,n)=1
2 deelt niet m-n
alleen PD'en over houdt?

(ik hoop dat dit duidelijk genoeg is )

Eh ja. Als je m en n zelf invoert, en ze voldoen aan die eisen, dan heb je per definitie
van primiviteit een primitief drietal. Dus je input moet goed zijn. Dus dat is alles idd. Mocht je terugwillen, dan kan je mijn verhaal gebruiken wat nu dus nutteloos is.

[JTW]

Ok!
Dankje!

[MSalters]

De truc zonder factorisatie is dat alle primitieve drietallen de vorm hebben
A=(2n+1), B=(A*A -1)/2, C=(A*A +1)/2
A is dus altijd het kleinste getal, terwijl C-B=1
9, 40, 41 is dus primitief (A=9, C-B=1 ) terwijl 9, 12, 15 het niet is. (C-B > 1)
------
Foutje, was andersom. Alle getallen met die vorm zijn primitief, en wel omdat
C-B=1. Stel namelijk dat (C,B) > 1, dan is (C-B) modulo (C,B) = 0. Dat betekent dat 1 modulo (C,B) = 0, en dat impliceert (C,B) = 1 wat in strijd is met de aanname dat (C,B) > 1.

[ Voor 36% gewijzigd door MSalters op 12-05-2004 17:38 . Reden: Redenatie omgedraaid. ]

[Verwijderd]

JTW schreef op 10 mei 2004 @ 22:09:
Ok!
Dankje!

Die eis die ik gaf, dat is eigenlijk niet de oorspronkelijke definitie van een primitief drietal.
De oorspronkelijke definitie is: Als a^2 + b^2 = c^2 met (a,b)=1 dan heet (a,b,c) primitief.
Een stelling zegt dan dat alle primitieve drietallen worden gegeven door die drietallen die aan bovengenoemde eis voldoen. Die eis nam ik dus meteen al als definitie van primitief drietal.
Het komt allemaal op hetzelfde neer, dus kijk gewoon of aan die eis is voldaan.

[Verwijderd]

MSalters schreef op 10 mei 2004 @ 22:10:
De truc zonder factorisatie is dat alle primitieve drietallen de vorm hebben
A=(2n+1), B=(A*A -1)/2, C=(A*A +1)/2
A is dus altijd het kleinste getal, terwijl C-B=1
9, 40, 41 is dus primitief (A=9, C-B=1 ) terwijl 9, 12, 15 het niet is. (C-B > 1)

dit is niet waar. (8,15,17) is primitief maar niet van de vorm die jij geeft.

[JTW]

MSalters schreef op 10 mei 2004 @ 22:10:
De truc zonder factorisatie is dat alle primitieve drietallen de vorm hebben
A=(2n+1), B=(A*A -1)/2, C=(A*A +1)/2
A is dus altijd het kleinste getal, terwijl C-B=1
9, 40, 41 is dus primitief (A=9, C-B=1 ) terwijl 9, 12, 15 het niet is. (C-B > 1)

Mijn leraar vertelde dit ook, maar zei erbij dat niet alle PD'en hiermee gevonden konden worden.
Als je beweert dat alle primitieve drietallen de vorm hebben van
A als kleinste, en B+1=C, dan klopt dat iig niet.
Er zijn namelijk ook andere PD'en, met een verschil tussen B en C dat groter is dan 1, bijvoorbeeld: 8,15,17

edit:
te laat

[ Voor 9% gewijzigd door JTW op 10-05-2004 23:01 ]

[Opi]

Waarschijnlijk heel offtopic, maar wat betekent de notatie (a,b) = 1? De enige gemene deler van a en b is gelijk aan 1?

[JTW]

OpifexMaximus schreef op 10 mei 2004 @ 23:02:
Waarschijnlijk heel offtopic, maar wat betekent de notatie (a,b) = 1? De enige gemene(gemeenschappelijke) deler van a en b is gelijk aan 1?

Precies