4 ms·
By the way, is it a secret to programmers that Pythagorean triples can be parametrised? I understand that the point of the code is to enumerate them without kn
by jordigh 8y ago
By the way, is it a secret to programmers that Pythagorean triples can be parametrised?
I understand that the point of the code is to enumerate them without knowing that they can be parametrised, but the parametrisation in this case is not so scary, so it's a fun bit of trivia for programmers (for mathematicians, it's more fundamental, as the Pythagorean parametrisation is an important prototype for counting rational points on elliptic curves, a fundamental problem in number theory).
https://en.wikipedia.org/wiki/Pythagorean_triple#Generating_a_triple https://en.wikipedia.org/wiki/Pythagorean_triple#Generating_...
Slightly less easy nor well-known amongst mathemticians (or at least, this is new to me), you can enumerate all primitive Pythagorean triples in a tree!
https://en.wikipedia.org/wiki/Tree_of_primitive_Pythagorean_triples https://en.wikipedia.org/wiki/Tree_of_primitive_Pythagorean_...
This tree is really interesting! I wonder where those matrices come from. The proof that it works is a boring mechanical check, but I'm now interested in how they were derived in the first place. This is a 20th century discovery, unlike the parametrisation which comes from antiquity. I think I'll be reading some papers about this.
- stabbles 8y agoThis was useful to me when doing Project Euler exercises, but I wouldn't know how to prove this generates all triples.
- jordigh 8y agoThe basic idea I like is, take x^2 + y^2 = z^2, but divide by z^2 to get (x/z)^2 + (y/z)^2 = 1. Now you're looking for the rational points on the unit circle. An important observation is that any two rational points define a line with rational slope. You know of one such rational point on the unit circle, say, (-1, 0). Now you can invert this process and pick a line with rational slope that goes through (-1,0). All lines with rational slope going through (-1,0) will hit another rational point on the circle, so you've found all rational points on the circle by this method, which include all primitive Pythagorean triples. When you work out this math, you recover the classical parametrisation, where the slope m/n of the line corresponds to the parameters, and this line-intersection method is a good inspiration for how to do the same with some higher-order curves such as elliptic curves, where it leads to the group law on them.
- pgtan 8y agoThere is a paper by Josef Rukavicka called "Dickson's Method for Generating Pythagorean Triples Revisited"[1]. It is a very nice proof without words. Based on it, the Project Euler solution was almost an oneliner in Prolog. [1] https://www.ejpam.com/index.php/ejpam/article/view/1844 https://www.ejpam.com/index.php/ejpam/article/view/1844
- pjmlp 8y agoLast time I bothered with calculus was around 1996, so yeah it isn't something that sticks around.
- Ar-Curunir 8y agoThis doesn't have anything to do with analysis-like techniques, and is closer to combinatorial/number-theoretic stuff that programmers are more likely to be familiar with.
- pjmlp 8y agoWhich on my case happened to be on that same year. The only math stuff I kept updated was denotional semantics and linear algebra, due to compiler and 3D papers that I regularly read, which is anyway not something any of my peers bothers to do.
- empath75 8y agoI used the Dickins method just naively and it seems to be about 10x faster than what they did here at generating 1000 triples.
- kareemadel000 8y agoAlso, Fibonacci numbers and Binet's formula https://en.wikipedia.org/wiki/Fibonacci_number#Binet's_formula https://en.wikipedia.org/wiki/Fibonacci_number#Binet's_formu...