A while back I came across a fascinating video on YouTube by Mathologer, which described a little-known pair of discoveries that were made in 2007 and 2008 relating to a connection between the Fibonacci sequence and the Pythagorean triples. I have embedded the video at the end of this article, where you can learn all about the discovery.
In this article I would like to give an overview of this relationship between the Pythagorean triples and the Fibonacci sequence. We will then implement an algorithm in Java 17 using Maven that will perform the calculation upon which the relationship is based, calling it the Pythagonacci Box Tree (what H. Lee Price in his 2008 article refers to as the “New Pythagorean Tree”.)
The Fibonacci Sequence
The Fibonacci Sequence is a series of numbers where each number is the sum of the two preceding ones. Mathematically, it is defined by the recurrence relation:
F(n) = F(n – 1) + F(n – 2)
Commonly it is represented with the following seed values:
F(0)=0, F(1)=1
However, for the purposes of this article we are going to offset the zero and begin with 1, 1.
The first four numbers in our Fibonacci sequence are therefore 1, 1, 2, 3.
Pythagorean Triples
Pythagorean Triples are sets of three positive integers a, b, and c, such that:
a2 + b2 = c2
These number sets form the sides of right-angled triangles, with c being the hypotenuse.
The first Pythagorean triple has values a = 3, b = 4 and c = 5, since:
32 + 42 = 52
The Relationship Between the Fibonacci Sequence and Pythagorean Triples
Starting with the set of the first four numbers in the Fibonacci sequence, { 1, 1, 2, 3 }, we curve them clockwise into a 2 x 2 matrix, we shall call this a box, as follows:
| 1 | 1 |
| 3 | 2 |
The structure of a box can therefore be defined as follows (we will call this the box definition):
| V-U | U |
| V+U | V |
We then denote each of these values as a separate variable as follows:
| a | b |
| d | c |
We can then apply three functions to these variables to produce the first Pythagorean triple:
F1 + F2 = F3
F1 = (a x d)2
F2 = (2 x b x c)2
F3 = (a x c + b x d)2
(1 x 3)2 + (2 x (1 x 2))2 = ((1 x 2)+(1 x 3))2
32 + 42 = 52
In the YouTube video (see below) you may notice that the order of variables a, b, c and d is slightly different. I have chosen to use a clockwise arrangement because it maps to the Fibonacci sequence.
We then construct three empty boxes and apply three different transformations to the original box to produce the seed blueprints for three child boxes: X, Y and Z, the original being the parent. Each of the three transformations begins by selecting two values from the parent and locating them in the children as indicated by the positions of the variables shown here:
| – | b |
| d | – |
| – | – |
| d | c |
| a | – |
| – | c |
It will help with the layout in the article if we visualise these three child boxes joined side-by-side. I have also added some colour to make it clearer what happens in the subsequent step.
| – | b | – | – | a | – |
| d | – | d | c | – | c |
The next step involves a transform on each of the child boxes where the values from the bottom row are moved up into the empty cells in the top row, as follows:
| d | b | d | c | a | c |
| – | – | – | – | – | – |
By reference to the box definition from above, we can then populate the empty cells in the bottom row thus:
| d | b | d | c | a | c |
| d+b+b | d+b | d+c+c | d+c | a+c+c | a+c |
Substituting the values for a, b, c and d from the parent box, we get the following:
| 3 | 1 | 3 | 2 | 1 | 2 |
| 5 | 4 | 7 | 5 | 5 | 3 |
Next, we assign the values in each of the child boxes to their own equivalent a, b, c, and d:
| ax | bx | ay | by | az | bz |
| dx | cx | dy | cy | dz | cz |
Finally, for each of the child boxes, when we apply the functions F1, F2 and F3 discussed above to the variables a, b, c and d, we ALWAYS get Pythagorean triples!
(a x d)2 + (2 x b x c)2 = (a x c + b x d)2
X: (3 x 5)2 + (2 x 1 x 4)2 = (3 x 4 + 1 x 5)2 => 152 + 82 = 172
Y: (3 x 7)2 + (2 x 2 x 5)2 = (3 x 5 + 2 x 7)2 => 212 + 202 = 292
Z: (1 x 5)2 + (2 x 2 x 3)2 = (1 x 3 + 2 x 5)2 => 52 + 122 = 132
Each child box can then be transformed respectively to generate three children of its own, and each child will always produce a NEW Pythagorean triple. Continuing indefinitely in this way constructs a Pythagonacci Box Tree, in which every single primitive Pythagorean triple will be produced EXACTLY ONCE.
The Relationship Between the Fibonacci Sequence and the Rational Numbers
As if that were not enough, there is another interesting outcome of the above algorithm that identifies a fundamental relationship between the Fibonacci sequence and the rational numbers.
If we consider each column of the boxes in turn and take the top row value as numerator and the bottom row values as denominator, then we arrive at rational numbers in the form a/d and b/c. It has been proven that if we apply this process to every box indefinitely, we will get every single rational number between zero and one EXACTLY ONCE!
Java Implementation
I thought that these results were incredible – that this one algorithm could produce all of the Pythagorean triples AND all of the rational numbers between zero and one, and that it all arises from the simplicity of the Fibonacci sequence. It led me to want to write an implementation of the algorithm in Java, and this is where we shall now turn.
Class: PythagonacciBox
The main class in our Java implementation is going to be called PythagonacciBox. It will need to contain the four values for the box itself. Since we will be using recursion to generate each subsequent row of child boxes, to avoid stack overflows we will also need to give it an altitude that decreases with each subsequent generation and stops recursing when it gets below zero. We will also give it an id that will help us to locate the box in the overall structure when we come to log its values.
public class PythagonacciBox {
private final Integer altitude;
private final Long[] values;
private final String id;
/**
* Constructor for root box.
*/
public PythagonacciBox(Integer altitude, Long[] values) {
this(altitude, values, null, "0");
}
public PythagonacciBox(Integer altitude, Long[] values,
PythagonacciBox parent, String relativeId) {
// Descend towards the bottom of the tree by one step:
this.altitude = altitude - 1;
if (values.length != 4) {
throw new IllegalArgumentException("values must be length 4");
}
this.values = values;
this.id = parent != null ? parent.getId() + relativeId : relativeId;
}
public String getId() {
return id;
}
}I’ve included a sanity check to ensure the values are the correct length. Notice that we have two constructors: One for the “root” box, and another for general use. The root box doesn’t have a parent, so it is a special case.
The id is going to represent a box’s address in the box tree. The root box will have an id of “0”. Child boxes will be denoted using X, Y or Z, appended to the parent box’s id. For example, if a box has an id of “0XYYXZ” it means that the box is located by going from the root box “0” to its child “0X”, to its child “0XY”, to its child “0XYY”, to its child “0XYYX” and finally to its child “0XYYXZ”.
We will use constants to represent the indices of the variable positions a, b, c and d within the array of values:
private static final int IX_A = 0;
private static final int IX_B = 1;
private static final int IX_C = 2;
private static final int IX_D = 3;We will then need three methods: one for the square-root of each of the functions F1, F2 and F3, so that we can print the Pythagorean triples in the format A2 + B2 = C2.
public long getPythagoreanTripleSideA() {
return values[IX_A] * values[IX_D];
}
public long getPythagoreanTripleSideB() {
return 2 * values[IX_B] * values[IX_C];
}
public long getPythagoreanTripleHypotenuse() {
return values[IX_A] * values[IX_C] + values[IX_B] * values[IX_D];
}Then we need to add a function that will print the Pythagorean triples, and another that will check that the box actually represents a Pythagorean triple. If it doesn’t, we will have it throw an exception.
public String getPythagoreanTripleString() {
return String.format("%d^2 + %d^2 ?= %d^2",
getPythagoreanTripleSideA(),
getPythagoreanTripleSideB(),
getPythagoreanTripleHypotenuse());
}
public boolean validateIsPythagoreanTriple() {
long a = getPythagoreanTripleSideA();
long b = getPythagoreanTripleSideB();
long c = getPythagoreanTripleHypotenuse();
boolean isValid = a * a + b * b == c * c;
if (!isValid) {
throw new IllegalStateException(id + " is invalid!\n" + this);
}
return true;
}To perform the initialisation of the boxes with the Fibonacci sequence from the first two values, we will include the following static function:
private static Long[] fibonacci2x2(long a, long b) {
long c = a + b;
Long[] newValues = new Long[4];
newValues[IX_A] = a;
newValues[IX_B] = b;
newValues[IX_C] = c;
newValues[IX_D] = c + b;
return newValues;
}We will override toString() to print the id, the Pythagorean triple and the values for the box:
@Override
public String toString() {
return String.format("%s: %s\n%d\t%d\n%d\t%d",
id, getPythagoreanTripleString(),
values[IX_A], values[IX_B],
values[IX_D], values[IX_C]);
}Record: PythagonacciBoxTriplet
To represent the child boxes of a PythagonacciBox we will be using a wrapper that combines three PythagonacciBoxrecord (a Java 14+ feature) called PythagonacciBoxTriplet (Note: we will be adding PythagonacciBox.toStringRecursive()PythagonacciBox.validateIsPythagoreanTripleRecursive()
public record PythagonacciBoxTriplet(PythagonacciBox x,
PythagonacciBox y, PythagonacciBox z) {
@Override
public String toString() {
return x.toString() + y.toString() + z.toString();
}
public String toStringRecursive() {
return x.toStringRecursive() +
y.toStringRecursive() +
z.toStringRecursive();
}
public boolean validateIsPythagoreanTripleRecursive() {
return x.validateIsPythagoreanTripleRecursive() &&
y.validateIsPythagoreanTripleRecursive() &&
z.validateIsPythagoreanTripleRecursive();
}
}Now, returning to our PythagonacciBox class, we can add a reference to the children. We will also add the code that will create the children, which we will implement using a lazy-loading pattern within the getter:
public class PythagonacciBox {
// ...
private PythagonacciBoxTriplet children;
// ...
public PythagonacciBoxTriplet getChildren() {
if (children == null) {
// Calculate children:
// X: Take values b and d, move d to the top row,
// then Fibonacci clockwise.
// . b -> d b -> d b
// d . -> . . -> d+b+b d+b
PythagonacciBox x = new PythagonacciBox(altitude,
fibonacci2x2(values[IX_D], values[IX_B]), this, "X");
// Y: Take values d and c, move them to the top row,
// then Fibonacci clockwise.
// . . -> d c -> d c
// d c -> . . -> d+c+c d+c
PythagonacciBox y = new PythagonacciBox(altitude,
fibonacci2x2(values[IX_D], values[IX_C]), this, "Y");
// Z: Take values a and c, move c to the top row,
// then Fibonacci clockwise.
// a . -> a c -> a c
// . c -> . . -> a+c+c a+c
PythagonacciBox z = new PythagonacciBox(altitude,
fibonacci2x2(values[IX_A], values[IX_C]), this, "Z");
this.children = new PythagonacciBoxTriplet(x, y, z);
}
return children;
}Finally, we will add PythagonacciBox.toStringRecursive() and PythagonacciBox.validateIsPythagoreanTripleRecursive() as referenced earlier in the PythagonacciBoxTriplet. A call to either of these methods will initiate a chain of events that will recursively populate all of the children until we reach the bottom of the tree, or in the case of the validation method, we hit a non-Pythagorean triple, which will result in an exception. For this reason, we will also add a test for whether we have reached the bottom of the tree to stop recursion. Note that although the methods are not directly recursive in themselves, the co-dependency between the equivalent methods in PythagonacciBoxPythagonacciBoxTriplet
public class PythagonacciBox {
// ...
private boolean isEndRecursion() {
return altitude < 0;
}
public String toStringRecursive() {
return toString() + (isEndRecursion() ?
"" : getChildren().toStringRecursive());
}
// ...
public boolean validateIsPythagoreanTripleRecursive() {
return validateIsPythagoreanTriple() &&
(isEndRecursion() ||
getChildren().validateIsPythagoreanTripleRecursive());
}
}Class: PythagonacciBoxFactory
We now have all that we need to execute a PythagonacciBox tree to arbitrary depth, given sufficient system resources. We could do this directly, but it would be cleaner to use a factory class that can also encapsulate things such as an array of default values for the root box and a default “maximum depth” to use as the initial altitude. We will call it maximum depth because if we call the validating method and if the starting values give rise to non-Pythagorean triples somewhere before the altitude reaches zero, an exception will be thrown, so we don’t guarantee that the maximum depth will be reached.
The factory class will also provide simplified method calls for variations of constructor parameters.
public class PythagonacciBoxFactory {
private static final Long[] DEFAULT_ROOT_BOX_VALUES =
new Long[]{1L, 1L, 2L, 3L};
private static final Integer DEFAULT_MAX_DEPTH = 5;
private final Integer maxDepth;
private final Long[] rootBoxValues;
private PythagonacciBoxFactory(Integer maxDepth, Long[] rootBoxValues) {
this.maxDepth = maxDepth != null ? maxDepth : DEFAULT_MAX_DEPTH;
this.rootBoxValues = rootBoxValues!= null ?
rootBoxValues: DEFAULT_ROOT_BOX_VALUES;
}
private PythagonacciBox createRootBox() {
return new PythagonacciBox(maxDepth, rootBoxValues);
}
public static PythagonacciBox create() {
return new PythagonacciBoxFactory(DEFAULT_MAX_DEPTH,
DEFAULT_ROOT_BOX_VALUES).createRootBox();
}
public static PythagonacciBox create(Integer maxDepth) {
return new PythagonacciBoxFactory(maxDepth, DEFAULT_ROOT_BOX_VALUES)
.createRootBox();
}
public static PythagonacciBox create(Long[] rootBoxValues) {
return new PythagonacciBoxFactory(DEFAULT_MAX_DEPTH, rootBoxValues)
.createRootBox();
}
public static PythagonacciBox create(Integer maxDepth, Long[] values) {
return new PythagonacciBoxFactory(maxDepth, values).createRootBox();
}
}Tests
If writing this project from scratch, we would begin adding tests early on, to benefit from the principles of test driven development. However, to simplify this article the test class has been left until the end. We will use JUnit 5. To our pom.xml we add the following:
<dependencies>
<dependency>
<groupId>org.junit.jupiter</groupId>
<artifactId>junit-jupiter-engine</artifactId>
<version>5.10.2</version>
<scope>test</scope>
</dependency>
</dependencies>We shall add tests that run the boxes to varying depths and perform validation on valid and invalid configurations. Here is our test class:
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.assertThrows;
import static org.junit.jupiter.api.Assertions.assertTrue;
public class PythagonacciBoxTest {
@Test
public void testDepth0() {
PythagonacciBox box = PythagonacciBoxFactory.create(0);
System.out.println(box.toStringRecursive());
}
@Test
public void testDepth1() {
PythagonacciBox box = PythagonacciBoxFactory.create(1);
System.out.println(box.toStringRecursive());
}
@Test
public void testDepth2() {
PythagonacciBox box = PythagonacciBoxFactory.create(2);
System.out.println(box.toStringRecursive());
}
@Test
public void testDepth3() {
PythagonacciBox box = PythagonacciBoxFactory.create(3);
System.out.println(box.toStringRecursive());
}
@Test
public void testDepth4() {
PythagonacciBox box = PythagonacciBoxFactory.create(4);
System.out.println(box.toStringRecursive());
}
@Test
public void testDepthDefault() {
PythagonacciBox box = PythagonacciBoxFactory.create();
System.out.println(box.toStringRecursive());
}
@Test
public void testValidateIsPythagoreanTripleRecursive() {
PythagonacciBox box = PythagonacciBoxFactory.create();
assertTrue(box.validateIsPythagoreanTripleRecursive());
}
@Test
public void testValidateIsPythagoreanTripleRecursiveStartWithDoubleDefault() {
// If you double the initial input from the default 1, 1, 2, 3,
// you also get Pythagorean triples.
PythagonacciBox box = PythagonacciBoxFactory
.create(new Long[]{2L, 2L, 4L, 6L});
assertTrue(box.validateIsPythagoreanTripleRecursive());
}
@Test
public void testValidateIsPythagoreanTripleRecursiveStartWithArbitraryFiboLikeSequence() {
// Start with an arbitrary sequence that satisfies V-U, U, V, V+U.
// This also gives you pythagorean triples.
PythagonacciBox box = PythagonacciBoxFactory
.create(new Long[]{29L, 29L, 58L, 87L});
assertTrue(box.validateIsPythagoreanTripleRecursive());
}
@Test
public void testValidateIsPythagoreanTripleRecursiveStartWithFirst4Primes() {
// It only generates pythagorean triples if the starting sequence
// is "Fibonacci-like".
PythagonacciBox box = PythagonacciBoxFactory
.create(new Long[]{2L, 3L, 5L, 7L});
assertThrows(IllegalStateException.class,
box::validateIsPythagoreanTripleRecursive);
}
}Some of the tests print their results to the console. Here is the output from testDepth1() for example, which reproduces the example introduced at the beginning of this article:
0: 3^2 + 4^2 ?= 5^2
1 1
3 2
0X: 15^2 + 8^2 ?= 17^2
3 1
5 4
0Y: 21^2 + 20^2 ?= 29^2
3 2
7 5
0Z: 5^2 + 12^2 ?= 13^2
1 2
5 3
You should now be able to go away and experiment with different starting values yourself. It was interesting to see that it seems to produce Pythagorean triples for any “Fibonacci-like” sequence, not just that which begins 1, 1, 2, 3. This shows us that it is the algorithm that is important, not merely the starting conditions (which almost sounds philosophical!)
YouTube Video
Below you can view the Mathologer YouTube video that gave me the idea for this post. Please take a moment to give the video a thumbs up: