Infinite Sequence Part V - Pythagorean Triple

Most of the time, if we think of sequence, it should be natural numbers. But this time, we change to geometry. An interesting geometry is Pythagorean triple. Pythagorean triple consists of 3 integer values which can be constructed a right triangle. A primitive Pythagorean triple is triple that all values in triple are coprime. Example of primitive Pythagorean triples are:

( 3,  4,  5) ( 5, 12, 13) ( 7, 24, 25)
( 8, 15, 17) ( 9, 40, 41) (11, 60, 61)
(12, 35, 37) (13, 84, 85) (16, 63, 65)

To generate a Pythagorean triple is easy, just pick 2 integer m and n where m > n. This is the formula to create Pythagorean triple.

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

Such as number is 2 and 1.

Side a = 2² - 1²   = 3
Side b = 2 * 2 * 1 = 4
Side c = 2² + 1²   = 5

Now we get (3, 4, 5) triple.

This is the class that represent Pythagorean triple.

//Fix: 2008-02-29 - Make class immutable
public class PythagoreanTriple {
    int _seed1;
    int _seed2;
    int _size;
    int _sideA;
    int _sideB;
    int _sideC;

    public int Seed1 {
        get { return _seed1; }
    }
    public int Seed2 {
        get { return _seed2; }
    }
    public int Size {
        get { return _size; }
    }
    public int SideA {
        get { return _sideA; }
    }
    public int SideB {
        get { return _sideB; }
    }
    public int SideC {
        get { return _sideC; }
    }
    public int Perimeter {
        get { return _sideA + _sideB + _sideC; }
    }

    public PythagoreanTriple() : this(1, 1, 1) { }
    public PythagoreanTriple(int seed1, int seed2) : this(seed1, seed2, 1) { }
    public PythagoreanTriple(int seed1, int seed2, int size) {
        _seed1 = seed1;
        _seed2 = seed2;
        _size = size;
        calculateTriple();
    }

    void calculateTriple() {
        int seed1pow2 = _seed1 * _seed1 * _size;
        int seed2pow2 = _seed2 * _seed2 * _size;

        _sideA = seed1pow2 - seed2pow2;
        _sideB = 2 * _seed1 * _seed2 * _size;
        _sideC = seed1pow2 + seed2pow2;
    }
    public override bool Equals(object obj) {
        PythagoreanTriple p = obj as PythagoreanTriple;
        if (p == null)
            return false;
        return _seed1 == p._seed1 && _seed2 == p._seed2 && _size == p._size;
    }
    public override int GetHashCode() {
        return _sideA;
    }
    public override string ToString() {
        return string.Format("({0}, {1}, {2})", _sideA, _sideB, _sideC);
    }
}

SideA, SideB, SideC represent 3 numbers of Pythagorean triple. Seed1 and Seed2 represent 2 input numbers to calculate the triple. And Size is multiplier of each side. For instance, if Size is 2, SideA, SideB, SideC are double.

To generate primitive Pythagorean triple, Seed1 and Seed2 must be coprime, Seed1+Seed2 must be odd value, and Size must be 1. To find whether 2 integers are coprime, that 2 integers must have Greatest Common Divisor (GCD) equals to 1. This is the formula to calculate GCD.

public static int Gcd(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

Put this function into your extension class.

Now start creating Pythagorean sequence. Just put this few lines of code to create class.

public class Pythagorean : BaseSequence<PythagoreanTriple> {
    protected override IEnumerable<PythagoreanTriple> Enumerate() {
        for (int m = 2; ; m++) {
            for (int n = (m % 2 == 0) ? 1 : 2; n < m; n += 2) {
                if (Math2.Gcd(m, n) == 1)
                    yield return new PythagoreanTriple(m, n);
            }
        }
    }
}

You can notice that if m is even, n starting number is odd, and vice versa. And n is incresed by 2 every turn. This makes m+n always be odd number. And before creating new triple, we check that m and n is coprime. Therefore, this class will generate sequence of only primitive Pythagorean triple.

To create non-primitive Pythagorean triple, you can set Size of PythagoreanTriple to any positive integer. To calculate Size, you can find from dividing target SideC with current SideC, or dividing target Perimeter with current Perimeter.

Here is example from projecteuler.net
Find product abc of Pythagorean triplet, for which a + b + c = 1000.

var p = new Pythagorean().First(x => 1000 % x.Perimeter == 0);
p = new PythagoreanTriple(p.Seed1, p.Seed2, 1000 / p.Perimeter);
Console.WriteLine(p.SideA * p.SideB * p.SideC);
//31875000

Example above, we find first Pythagorean triple which its perimeter can be the divisor of 1000. Then, we create new Pythagorean triple from the triple we just found with size 1000/perimeter. Finally, print result sideA * sideB * sideC.

If p is the perimeter of a right angle triangle, {a, b, c}, which value, for p ≤ 1000, has the most solutions?

int[] list = new int[1000];
int maxSeed1 = (int)Math.Sqrt(500); //maxSeed1 = Sqrt(targetPerimeter/2)

new Pythagorean().TakeWhile(p => p.Seed1 <= maxSeed1).ForEach(p => {
    for (int i = p.Perimeter; i < 1000; i += p.Perimeter)
        list[i]++;
});
Console.WriteLine(0.To(999).OrderByDescending(x => list[x]).First());
//840

This problem, we must find how many items in the sequence we should generate. We should generate until last triple which its perimeter <= 1000. To find last seed1 value that its perimeter = 1000, use formula Sqrt(targetPerimeter/2). Now, for each triple we generate, mark in the list that which number its perimeter can be. And then sort the list, to find which number has the highest mark.

This post is an end of infinite sequence series. Next, we will go to totally different extension methods topic, which is extension methods for delegate types.