Problem: Consider the picture below (image credits to Project Euler)

The four triangles are assumed to be right triangles. When placed in the arrangement as shown, there is a hole in the middle. Consider all right triangles that have perimeter less than 100,000,000, how many of the right triangles make a hole such that the hole can be used to tile the larger resulting square?

For any right triangle, let the smaller leg be “a”, the longer leg be “b”, and the hypotenuse “c”, so that any triangle can be identified by a tuple (a, b, c). It then follows that the hole is a square with side lengths (b-a). From the image, it also follows that the larger square has side lengths equal to the hypotenuse of the constituent triangles. For the larger square to be able to be tiled by the hole, its side lengths must then be an integer multiple of the hole’s side lengths, or put simply: c = (b-a)k, for some k. This would be a simple test, supposing that you could generate all pythagorean triples (a, b, c) such that the perimeter is within the bounds of the question.

Given the problem parameters, it wouldn’t be prudent to iterate blindly over “a”, “b”, and “c” to generate the triples. The easiest way I know how is by Euclid’s formula (http://en.wikipedia.org/wiki/Pythagorean_triple#Generating_a_triple). For any pair (m, n), the following are always a Pythagorean triple:

a = m^2 – n^2

b = 2mn

c = m^2 + n^2

You can compute a^2 + b^2 = c^2 to see for yourself. Moreover, this formula is complete, in the sense that you can generate all primitive Pythagorean triples with this, primitive triples being (a, b, c) such that the greatest common divisor of the triple is 1. The triple is guaranteed to be primitive as long as (m, n) are coprime and of opposite parity. Lastly, as we all know, given a Pythagorean triples, the same multiple of each length is also a Pythagorean triple. Armed with this, we can generate all triples.

To make sure that that each primitive we generate is unique, assume that m > n. This also reduces the number of times we have to iterate considerably. Again, the process we’ll go through generates primitive triples, but it is a simple matter to calculate how many similar triangles also fit the perimeter bound, simply by dividing 100000000 by the primitive triple’s perimeter.

Here is the code that accomplishes all that.

for(n = 1; n < 10000; n++){
    for(m = n+1; m*m+n*n <= 100000000; m++){
        if((m-n)%2 == 1){
            if(gcd(m, n) == 1){
                x = m*m - n*n;
                y = 2*m*n;
                z = m*m + n*n;
                if(x+y+z < 100000000){
                    if(z%(abs(x-y)) == 0) count+=(100000000/(x+y+z));
                }
            }
        }
    }
}

GCD is done with this little code snippet. It’s very efficient and very useful to have:

int gcd(int a, int b){
    if(b == 0) return a;
    else return gcd(b, a%b);
}

In the end, count = 10057761