Pythagorean Triplets

A Pythagorean triplet is a set of three natural numbers, $a$ $b$ $c$, for which, $a^2$ + $b^2$ = $c^2$.  Even more interesting, a Primitive Pythagorean Triplet is a is considered primitive if, and only if, $a, b,$ and $c$ share no common divisor. That being said, a non-primitive pythagorean triple would then satisfy the rule $(ka)^2 + (kb)^2 = (kc)^2$ where $k > 1$ and $k$ is a whole number. So, given a primitive triple, we can use it to generate the non-primitive's.

I thought it would be a fun project to create a function to generate the primitive Pythagorean triples. And, after recently talking about the Binary Search Tree, I thought using a ternary tree to show this might be a good expansion on the topic.

There were 3 different method's I used to create this tree. We'll start with using the matrices discovered by B. Berggren. These three matrices are as follows:
$$A = \left| \begin{array}{ccc} 1 & -2 & 2 \\ 2 & -1 & 2 \\ 2 & -2 & 3 \end{array} \right| B = \left| \begin{array}{ccc} 1 & 2 & 2 \\ 2 & 1 & 2 \\ 2 & 2 & 3 \end{array} \right| C = \left| \begin{array}{ccc} -1 & 2 & 2 \\ -2 & 1 & 2 \\ -2 & 2 & 3 \end{array} \right|$$ If we multiply these three matrices by a column vector whose components form a Pythagorean triple, more specifically a primitive Pythagorean triplet, then the result is another column vector whose components are a different primitive Pythagorean triple. With these matices we can create three more primitive Pythagorean triple "children" from any set of primitive triples. Starting with a root of $(3, 4, 5)$ and continuing this process with each resulting set, eventually, all primitive Pythagorean triples are generated with no repetitions. This is represented well in a ternary tree where we would just repeat the transformation in each subtree. (Wiki)

For this particular project, I decided to work in C# so, beginning with the node class, here is the code that represents generating this tree:

public class node {
    private int a;
    private int b;
    private int c;
    private node left;
    private node middle;
    private node right;

    public node(int x, int y, int z) {
        a = x;
        b = y;
        c = z;
    }

    public int getValue(string identifier) {
        int value = 0;
        if (identifier == "a")
        { value = a; }
        else if (identifier == "b")
        { value = b; }
        else if (identifier == "c")
        { value = c; }
        return value;
    }

    public void setLeft(node newNode) {
        left = newNode;
    }

    public void setMiddle(node newNode)
    {
        middle = newNode;
    }

    public void setRight(node newNode)
    {
        right = newNode;
    }
}

And, here is the function to generate the tree itself. I decided to make the tree stop generating when all three of the values were greater than 500 but, it could go on indefinitely.

public static node createPrimitiveTreeB(int x, int y, int z) {
    node root = new node(x, y, z);
    if (root.getValue("a") > 500 && root.getValue("b") > 500 && root.getValue("c") > 500) {  // Stop the tree eventually
        return root;
    } else {
        //Berggren's matrices
        int a1, b1, c1, a2, b2, c2, a3, b3, c3;

        //Left Child
        a1 = (-1 * root.getValue("a")) + (2 * root.getValue("b")) + (2 * root.getValue("c"));
        b1 = (-2 * root.getValue("a")) + root.getValue("b") + (2 * root.getValue("c"));
        c1 = (-2 * root.getValue("a")) + (2 * root.getValue("b")) + (3 * root.getValue("c"));

        root.setLeft(createPrimitiveTreeB(a1, b1, c1));

        //Middle Child
        a2 = root.getValue("a") + (2 * root.getValue("b")) + (2 * root.getValue("c"));
        b2 = (2 * root.getValue("a")) + root.getValue("b") + (2 * root.getValue("c"));
        c2 = (2 * root.getValue("a")) + (2 * root.getValue("b")) + (3 * root.getValue("c"));

        root.setMiddle(createPrimitiveTreeB(a2, b2, c2));

        //Right Child
        a3 = (root.getValue("a")) + (-2 * root.getValue("b")) + (2 * root.getValue("c"));
        b3 = (2 * root.getValue("a")) + (-1 * root.getValue("b")) + (2 * root.getValue("c"));
        c3 = (2 * root.getValue("a")) + (-2 * root.getValue("b")) + (3 * root.getValue("c"));

        root.setRight(createPrimitiveTreeB(a3, b3, c3));

        return root;
    }
}

Similarly to Berggren, other mathematicians (Price in this case) came up with a set of matrices for generating the triples. Price's matrices are as follows:
$$A = \left| \begin{array}{ccc} 2 & 1 & -1 \\ 2 & 2 & 2 \\ 2 & -1 & 3 \end{array} \right| B = \left| \begin{array}{ccc} -2 & 1 & 1 \\ 2 & -2 & 2 \\ 2 & 1 & 3 \end{array} \right| C = \left| \begin{array}{ccc} -2 & 1 & 1 \\ 2 & -2 & 2 \\ 2 & 1 & 3 \end{array} \right|$$ Operating under the same concept, I didn't need to make much changes to the function in order to generate the tree with these matrices. These transformations should generate the same tree. For the code below, I just show the modifications to the "createPrimitiveTreeB" function above (I renamed this one to "createPrimitiveTreeP").

//Price's matrices
int a1, b1, c1, a2, b2, c2, a3, b3, c3;

// Left Child
a1 = (2 * root.getValue("a")) + (root.getValue("b")) + (-1 * root.getValue("c"));
b1 = (-2 * root.getValue("a")) + (2 * root.getValue("b")) + (2 * root.getValue("c"));
c1 = (-2 * root.getValue("a")) + root.getValue("b") + (3 * root.getValue("c"));

root.setLeft(createPrimitiveTreeP(a1, b1, c1));

// Middle Child
a2 = (2 * root.getValue("a")) + root.getValue("b") + root.getValue("c");
b2 = (2 * root.getValue("a")) + (-2 * root.getValue("b")) + (2 * root.getValue("c"));
c2 = (2 * root.getValue("a")) + (-1 * root.getValue("b")) + (3 * root.getValue("c"));

root.setMiddle(createPrimitiveTreeP(a2, b2, c2));

// Right Child
a3 = (2 * root.getValue("a")) + (-1 * root.getValue("b")) + root.getValue("c");
b3 = (2 * root.getValue("a")) + (2 * root.getValue("b")) + (2 * root.getValue("c"));
c3 = (2 * root.getValue("a")) + root.getValue("b") + (3 * root.getValue("c"));

root.setRight(createPrimitiveTreeP(a3, b3, c3));

For the final method of generating the tree, and in my opinion the most fun, we will be using the Fibonacci Sequence. If you don't know what the Fibonacci sequence is, I talk about it in this post.

To do this, we follow a simple method of generating the Fibonacci numbers and retrieving the triples from these numbers. This is done by creating, what we'll call, a "Fibonacci Box". This matrix consists of four positive integers $q$, $q'$, $p$, $p'$ where $q$ and $q'$ are any two coprime numbers. In order to get $p$ and $p'$, we follow the Fibonacci Rule where $q' + q = p$ and $q + p = p'$, giving us a generalized Fibonacci sequence.
$$\left| \begin{array}{cc} q & q' \\ p & p' \end{array} \right|$$ From this initial matrix, we can generate three "children" by using this method:
$$\left| \begin{array}{cc} q & q' \\ p & p' \end{array} \right| \Rightarrow \left| \begin{array}{cc} (p' - q') & q' \\ p' & (2p' - q') \end{array} \right|, \left| \begin{array}{cc} p' & q' \\ (q' + p') & (2p' + q') \end{array} \right|, \left| \begin{array}{cc} q' & p' \\ (p' + q') & (2q' + p') \end{array} \right|$$ Now, from these matrices, we need to create the pythagorean triplets themselves. Given the formula $a = q'p', b = 2qp, c= pp' - qq'$, we can generate a set of triplets per Fibonacci Box. Just like Berggren and Price's matrices, we will be generating all the triples with no repetitions when using this method. For this tree, I thought it would be appropriate to create a new type of node, this gives us a new class:

public class boxNode {
    private int[,] fibBox = new int[2,2];
    private int a;
    private int b;
    private int c;
    private boxNode left;
    private boxNode middle;
    private boxNode right;

    public boxNode(int[,] box)
    {
        fibBox = box;
        a = fibBox[0, 1] * fibBox[1, 1];
        b = 2 * fibBox[0, 0] * fibBox[1, 0];
        c = (fibBox[1, 0] * fibBox[1, 1]) - (fibBox[0, 0] * fibBox[0, 1]);
    }

    public int getValue(string identifier)
    {
        int value = 0;
        if (identifier == "a")
        { value = fibBox[0,1] * fibBox[1,1]; }
        else if (identifier == "b")
        { value = 2 * fibBox[0, 0] * fibBox[1, 0]; }
        else if (identifier == "c")
        { value = (fibBox[1, 0] * fibBox[1, 1]) - (fibBox[0, 0] * fibBox[0, 1]); }
        return value;
    }

    public int[,] getBoxValue() {
        return fibBox;
    }

    public void setLeft(boxNode newNode) {
        left = newNode;
    }

    public void setMiddle(boxNode newNode) {
        middle = newNode;
    }

    public void setRight(boxNode newNode) {
        right = newNode;
    }
}

And, a function using this method to generate the entire tree.

public static boxNode createPrimitiveTreeF(int[,] fibBox) {
    boxNode root = new boxNode(fibBox);
    if (root.getValue("a") > 500 && root.getValue("b") > 500 && root.getValue("c") > 500) {
        return root;
    } else {
        //Using Fibonacci Box
        int[,] parentBox = root.getBoxValue();
        int[,] fibBox1 = new int[2, 2];
        int[,] fibBox2 = new int[2, 2];
        int[,] fibBox3 = new int[2, 2];

        // Box Properties: [0,0] = [1,0] - [0, 1]; [1, 1] = [0, 0] + [1, 0]
        fibBox1[0, 0] = parentBox[1, 1] - parentBox[0, 1];
        fibBox1[0, 1] = parentBox[0, 1];
        fibBox1[1, 0] = parentBox[1, 1];
        fibBox1[1, 1] = (parentBox[1, 1] - parentBox[0, 1]) + parentBox[1, 1];

        root.setLeft(createPrimitiveTreeF(fibBox1));

        // Box Properties: [1, 0] = [0, 1] + [0, 0]; [1, 1] = [0, 0] + [1, 0]
        fibBox2[0, 0] = parentBox[1, 1];
        fibBox2[0, 1] = parentBox[0, 1];
        fibBox2[1, 0] = parentBox[0, 1] + parentBox[1, 1];
        fibBox2[1, 1] = parentBox[1, 1] + (parentBox[0, 1] + parentBox[1, 1]);

        root.setMiddle(createPrimitiveTreeF(fibBox2));

        // Box Properties: [1, 0] = [0, 1] + [0, 0]; [1, 1] = [0, 0] + [1, 0]
        fibBox3[0, 0] = parentBox[0, 1];
        fibBox3[0, 1] = parentBox[1, 1];
        fibBox3[1, 0] = parentBox[1, 1] + parentBox[0, 1];
        fibBox3[1, 1] = parentBox[0, 1] + (parentBox[1, 1] + parentBox[0, 1]);

        root.setRight(createPrimitiveTreeF(fibBox3));

        return root;
    }
}

We can test the functions with the code below, putting a breakpoint at "ReadLine" and examining the local variables.

static void Main(string[] args) {
    node berggrenTree = createPrimitiveTreeB(3, 4, 5); // root of tree must be initialized with first primitive triple
    node priceTree = createPrimitiveTreeP(3, 4, 5); // root of tree must be initialized with first primitive triple
    int[,] initFibBox = new int[2,2]; 
    initFibBox[0, 0] = 1;
    initFibBox[0, 1] = 1;
    initFibBox[1, 0] = 2;
    initFibBox[1, 1] = 3;
    boxNode fibTree = createPrimitiveTreeF(fibBox); // root of tree must be initialized with beginning of Fibonacci sequence
    Console.ReadLine();
}

After running this code, you will be able to see a ternary tree and the primitive Pythagorean triples that it generates in your local variables. I thought this might be an interesting topic as it gives more insight into using trees, as well as a look at implementing matrices and the Fibonacci sequence in a useful way (provided that generating the primitive Pythagorean triplets is useful to you). I think it's especially interesting to see how the Fibonacci sequence can be used to create these triples and it might be worth playing around with your initial Fibonacci Box to see the different trees you can create. You can use any numbers to create the initial box as long as it satisfies these conditions: $q'$ and $p'$ are both odd, either $q$ or $p$ is even and $q < p$ , $q' < p'$. Of course being a "Fibonacci" box, the values must maintain the properties of the sequence as stated above.

Any questions, comments and/or suggestions are appreciated.