A binary tree of all Pythagorean triples
179 points
2 days ago
| 6 comments
| richardt.io
| HN
sevensor
1 day ago
[-]
This is wonderful! I’d somehow missed the classical enumeration of Pythagorean triples. I learned them as magic numbers. That structure alone is worth the price of admission.
reply
dpunjabi24
1 day ago
[-]
Beautiful. Thanks for sharing.
reply
keithalewis
1 day ago
[-]
There are Pythagorean triples (a, b, c) for which there do not exist integers m, n with a = m^2 - n^2, b = 2mn, c = m^2 + n^2.
reply
tromp
22 hours ago
[-]
But all such triples are non-primitive. I.e. they are of the form (ka, kb, kc) with k>1. So all Pythagorean triples can be generated as a scaled primitive triple (a,b,c) that is generated by Euclid's formula from m,n.
reply
FredrikMeyer
23 hours ago
[-]
Learned something new today. For other interested: https://en.wikipedia.org/wiki/Pythagorean_triple#Generating_...
reply
matt3210
1 day ago
[-]
Very nice! nit: website isn’t mobile friendly
reply
lollobomb
1 day ago
[-]
Wow, this is extremely cool! Only problem, the JS slows my Firefox almost to freezing, is it normal?
reply
hakmem
1 day ago
[-]
Yes, this is normal. I am sorry, I am working on a more efficient implementation.

The JavaScript of this page does a lot of number crunching.

It is actually doing arithmetic on the Stern-Brocot tree. It is all written in ClojureScript and not really optimized yet. I mention in the paper that I do not even use TCO.

Anyway, thank you - and all the people here - for the kind words! I am so happy that my article was so well received today.

reply
akomtu
1 day ago
[-]
A simple trick to solve nearly all freezing problems: move the computations to a background thread, aka Worker in JS terms.
reply
aabhay
1 day ago
[-]
Another trick — use comlink (https://github.com/GoogleChromeLabs/comlink) to make the worker thread into essentially an async API of your local methods.
reply
not2b
1 day ago
[-]
You changed the article's title to an incorrect one. The tree of primitive Pythagorean triples is ternary, not binary. Each node has three children.
reply
feoren
1 day ago
[-]
Keep reading. The Barning-Hall tree is ternary, but this article is mostly devoted to the Stern-Brocot tree, which is binary.
reply
generationP
1 day ago
[-]
Both conventions are valid. You call it binary when you view it as a rooted tree, or ternary if you view it just as a graph.
reply
nyrikki
1 day ago
[-]
But it _all_ triples?

> I sketch how the stereographic projection of the Stern–Brocot tree forms an ordered binary tree of Pythagorean triples, which can be used to compute best approximations of turn angles of points on the circle and finally trigonometric functions

The permutation and stack problem in the page seem to indicate this is a potential method for approximations, but insufficient for _all_

That said I am reading this on mobile and may have missed something.

reply
not2b
1 day ago
[-]
The ternary tree contains all primitive triples (where the GCD of the terms is 1), where a<b<c. So it contains (3,4,5) but not (6,8,10) or (4,3,5).
reply
nyrikki
1 day ago
[-]
Yes, but the binary projection does not according to the link.

345 and 435 would require two binary trees.

reply
AnotherGoodName
1 day ago
[-]
I think skipping transposed values is fine though. You could just mirror the output at 45degrees for that if you wanted it. It does hit all distinct triples including the multiples of triples so it’s more inclusive of everything than the ternary tree.
reply
hakmem
1 day ago
[-]
You can see both triples are contained in one binary tree using the big diagram in section 3. The triple [3 4 5] has the "path" RR. The triple [4 3 5] the path R.
reply
ColinWright
1 day ago
[-]
From the article:

"I sketch how the stereographic projection of the Stern–Brocot tree forms an ordered binary tree of Pythagorean triples ..."

... and ...

"Before that, I briefly recapitulate the classical enumeration of Pythagorean triples and the ternary Barning–Hall tree."

So this article is about the binary tree representation.

reply