Problem 9: Special Pythagorean triplet

Problem:

Please find the problem here.

Solution:

Along our usual line-of-thought, we would think about brute force again. But this time brute force is not so easy anymore since we need to find out a good pair that work. We can still try all possible pairs, but that will spend a lot of time on the unnecessary search. Turn out, iterating through the list of all Pythagorean triplet is not hard at all, as we can see shortly.

First, let's define primitive Pythagorean triplet be the Pythagorean triplet which is relatively prime. (i.e. GCD(a, b, c) = 1). Suppose we have a non-primitive Pythagorean triplet, we can divide every number by their GCD to obtain one. In some sense, primitive Pythagorean triplet spans the Pythagorean triplets.

The set of primitive Pythagorean triplet can be enumerated through the tree of primitive Pythagorean triplet found in wiki. What is not mentioned in the wiki is that the sum of the Pythagorean triplet must be increasing when we descend down the tree as we will show here:

The sum of the three numbers can be obtained by pre-multiplying the row vector (1, 1, 1). Thus the child node's sum can be obtained as:
(1,1,1)(d, e, f)' = (1,1,1)A(a,b,c) = 5a-5b+7c

Now we know a^2 + b^2 = c^2. Therefore c = sqrt(a^2 + b^2) > b. 5a - 5b + 7c > 5a - 5b + 6b + c = 5a + b + c>  a + b + c.

So we know the child sum is greater than the parent sum.

We can prove the other two matrices similarly. With that, we can be sure that we have found all primitive Pythagorean triples by doing a simple Breadth First Search on the tree and stop descending when sum exceed 1,000. With that we can check whether a particular triple works or not. The code will look like this.

namespace Euler
{
    using System;
    using System.Collections.Generic;
    using System.Linq;

    internal static partial class Program
    {
        public static void Problem009()
        {
            foreach (var triple in GetPrimitivePythTriples(1000))
            {
                int tripleSum = triple.Item1 + triple.Item2 + triple.Item3;
                if (1000 % tripleSum == 0)
                {
                    int scale = 1000 / tripleSum;
                    Console.WriteLine(scale * scale * scale * triple.Item1 * triple.Item2 * triple.Item3);
                    return;
                }
            }
        }


        public static IEnumerable<Tuple<int, int, int>> GetPrimitivePythTriples(int sumMax)
        {
            var root = new Tuple<int, int, int>(3, 4, 5);
            Queue<Tuple<int, int, int>> bfsQueue = new Queue<Tuple<int, int, int>>();
            bfsQueue.Enqueue(root);
            while (bfsQueue.Count > 0)
            {
                var visiting = bfsQueue.Dequeue();
                int a = visiting.Item1;
                int b = visiting.Item2;
                int c = visiting.Item3;

                if (a + b + c <= sumMax)
                {
                    yield return visiting;
                    bfsQueue.Enqueue(Tuple.Create(
                        1 * a - 2 * b + 2 * c,
                        2 * a - 1 * b + 2 * c,
                        2 * a - 2 * b + 3 * c));
                    bfsQueue.Enqueue(Tuple.Create(
                        1 * a + 2 * b + 2 * c,
                        2 * a + 1 * b + 2 * c,
                        2 * a + 2 * b + 3 * c));
                    bfsQueue.Enqueue(Tuple.Create(
                        -1 * a + 2 * b + 2 * c,
                        -2 * a + 1 * b + 2 * c,
                        -2 * a + 2 * b + 3 * c));
                }
            }
        }
    }
}

Note the use of yield return. This is a very powerful construct in C# that allow a method the sequence generating function a to become an iterator object with all the state keeping work done by the compiler. The best explanation of the yield feature (not necessarily the most precise, but the most understandable one) is found here.

Great feature comes with great responsibility when using it, you can trip yourselves up if you are not careful - typical mistake is iterating the sequence twice, you will do all the computation twice. Caching them in a list or array if you need to iterate more than once.

Answer: 31875000