Comment by jordigh | Hacker News Reader

Comment by jordigh | Hacker News Reader

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_...

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_...

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.

This was useful to me when doing Project Euler exercises, but I wouldn't know how to prove this generates all triples.

The 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.

There 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

Also, Fibonacci numbers and Binet's formula

https://en.wikipedia.org/wiki/Fibonacci_number#Binet's_formu...

I used the Dickins method just naively and it seems to be about 10x faster than what they did here at generating 1000 triples.

Last time I bothered with calculus was around 1996, so yeah it isn't something that sticks around.

This 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.

Which 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.

Reply on news.ycombinator.com