The Tree of Primitive Pythagorean Triples

The tree of primitive Pythagorean triples is an infinite family tree with 3-4-5 at the root, in which every triple has exactly three children, found by multiplying it by three fixed matrices. First published by B. Berggren in 1934, and published again by F. J. M. Barning (1963) and A. Hall (1970), it contains every primitive triple exactly once.

So the Berggren tree, also called the Barning or Hall tree, is a second complete way to generate primitive triples, alongside Euclid's formula. Unlike Euclid's formula, it needs no choices: each triple simply produces the next generation.

The three matrices

Write a primitive triple as a column (a, b, c) with the odd leg first, so a is odd and b is even. (Exactly one leg of a primitive triple is even, so this is always possible.) The three Berggren matrices are:

Multiplying a matrix by a column just means: each row of the matrix tells you how to mix a, b and c. The row 2, −1, 2, for example, means "2a − b + 2c". Written out without matrices, the three children of (a, b, c) are

You don't need to know anything about matrices to use the tree: these nine little formulas are all there is.

How to compute the children of a triple

Try one yourself before opening the solution.

The tree to depth 3

Applying the three matrices again and again builds the tree level by level. Level k has 3^k triples, so the first four levels hold 1 + 3 + 9 + 27 = 40 different primitive triples:

The same tree as a table, with the path from the root to each triple, reading the matrices in the order they are applied:

The hypotenuses grow quickly. The smallest at depth k lies on the all-A branch and equals 2k² + 6k + 5 (5, 13, 25, 41, …), while the largest lies on the all-B branch: 5, 29, 169, 985, each about 5.83 times the one before. That ratio tends to 3 + 2√2 ≈ 5.828. So the tree is not in order of size: to list triples by hypotenuse, use the list of Pythagorean triples instead.

Patterns along the three edges

Following the same matrix over and over traces out the edges of the tree, and each edge is a famous family:

• Always A gives the triples whose hypotenuse is one more than the even leg: 5-12-13, 7-24-25, 9-40-41 and so on. These are exactly the triples from Pythagoras' formula, (2k + 1, 2k² + 2k, 2k² + 2k + 1).
• Always C gives the triples whose hypotenuse is two more than the odd leg: 15-8-17, 35-12-37, 63-16-65. These come from Plato's formula with even k; the even leg goes up by 4 each time.
• Always B gives triangles whose legs differ by 1: 21-20-29, 119-120-169, 697-696-985. They get closer and closer to the isosceles right triangle, and their hypotenuses 5, 29, 169, 985 are every other Pell number (0, 1, 2, 5, 12, 29, 70, 169, …, in which each term is twice the previous one plus the one before).

The same tree with Euclid's m and n

Every primitive triple comes from Euclid's formula with a unique pair (m, n). In terms of those two numbers, the matrices become even simpler:

The root 3-4-5 is (2, 1). Its children are (3, 2), (5, 2) and (4, 1), which Euclid's formula turns into 5-12-13, 21-20-29 and 15-8-17, exactly as before. Along the all-B branch the pairs are (2, 1), (5, 2), (12, 5), (29, 12): consecutive Pell numbers. This version is the easiest one to run in your head.

Walking back up: the parent of a triple

The process also runs backwards. For any primitive triple other than 3-4-5, with the odd leg first, its parent is

The signs inside the absolute values tell you which matrix produced the triple: if both are positive it is a B-child; if the first is negative it is a C-child; if the second is negative it is an A-child.

Applied to 3-4-5 itself, the formula gives (1, 0, 1), which is not a triangle: the root has no parent.

Why every primitive triple appears exactly once

Here is a sketch of the proof, in five steps.

1. Children are Pythagorean triples. Each matrix keeps the quantity a² + b² − c² unchanged. For B, expanding the squares gives (a + 2b + 2c)² + (2a + b + 2c)²= 5a² + 5b² + 8c² + 8ab + 12ac + 12bc(2a + 2b + 3c)²= 4a² + 4b² + 9c² + 8ab + 12ac + 12bc and the difference is exactly a² + b² − c². A and C work the same way. So if a² + b² − c² = 0 for the parent, it is 0 for every child.
2. Children are primitive, with positive sides and the odd leg first. All three matrices have whole-number inverses (their determinants are 1 or −1), so any common factor of a child would also divide its parent. Every entry is positive because c is bigger than each leg, and working with remainders mod 2 shows the odd leg stays odd.
3. Every primitive triple except 3-4-5 has a parent, given by the formula above, and the parent's hypotenuse is smaller: 3c − 2a − 2b < c because a + b > c (the two legs together are longer than the hypotenuse), and it is positive because a + b is at most √2 c, which is less than 1.5c. A short calculation shows the formula only produces a zero side for 3-4-5 itself.
4. The parent is unique. Which matrix made a triple depends only on its shape, as the figure below shows, so no triple can be the child of two different parents, and the three children of one parent are always different.
5. Every chain of parents ends at the root. The hypotenuse drops at every step, and whole numbers cannot drop forever, so climbing up must stop, and the only place it can stop is 3-4-5. Every primitive triple is therefore reached from the root by exactly one path.

The two dividing angles are not random: 36.87° and 53.13° are the angles of the 3-4-5 triangle itself, and the root sits exactly on the border between the A and B wedges. We also checked the result by computer: growing the tree with every hypotenuse up to 20,000 produces 3,186 triples with no repeats, exactly the same 3,186 primitive triples that a brute-force search finds.

History and other trees

The tree was first published by the Swedish mathematician B. Berggren in 1934, in a paper titled "Pytagoreiska trianglar". The Dutch mathematician F. J. M. Barning described it again in 1963, and A. Hall wrote about it in English in 1970 in "Genealogy of Pythagorean Triads", which is why it goes by several names. It is not the only tree of its kind: H. Lee Price published a different set of three matrices in 2008 that also generates every primitive triple exactly once from 3-4-5, in a different order. (The Pythagoras tree, a fractal made of squares, is something else entirely.)

For a quick way to produce lots of triples without matrices, use the Pythagorean triples generator, and for the bigger picture, start at the Pythagorean triples hub.