[ prog / sol / mona ]

prog


e and the Stern-Brocot tree

53 2021-03-28 04:56

Just realized the Stern-Brocot tree being the list of all coprime numbers could be used to generate the pythagorean triples (uint a,b,c such that a²+b²=c²). We need to take only the right subtree where every m > n.
Euclide's formula to generate a pythagorean triple, with m and n coprimes:

a = m²-n², b = 2mn, c = m²+n²

If we need only primitive pythagorean triples then we just need to filter out the fractions where both m and n are odd.

54


VIP:

do not edit these