Project Euler 94: Investigating almost equilateral triangles with integral sides and area.

I can realy feel that the problems become harder and harder. Problem 94 of Project Euler took me a good while to figure out. The problem is easy to understand and reads

It is easily proved that no equilateral triangle exists with integral length sides and integral area. However, the
5-5-6 has an area of 12 square units.

We shall define an almost equilateral triangle to be a triangle for which two sides are equal and the third differs by no more than one unit.

Find the sum of the perimeters of all almost equilateral triangles with integral side lengths and area and whose perimeters do not exceed one billion (1,000,000,000).

We are dealing with a triangle with two sides of length a and one side of length b = a-1 or b = a+1. I will treat these as two different cases for the next paragraf or two.

Case: b = a+1

Using some basic geometry we know that the area of a triangle is A = h*b/2 where h is the height and b is the base. If we draw the height of the triangle we end up with two right angled triangles, and thus we can calculate the height using Pythagoras theorem which states that

or if we substitute b with a

Even though it at this point is not clear, we can in fact turn this equation into Pell’s equation which we have dealt with in Problem 66.

We do that by first by squaring and combining terms

The by multiplying by 3 we get

We can form a square of (3a – 1) such that we have

The dividing by 4 and rearranging we get

Substituting (3a -1)/2 = x and h = y we get

which is indeed Pell’s equation. So in other words we need to solve Pell’s equation in order to get answers for the question. I will get back to that once I have covered the other case

Case: b = a-1

You can make the exact same calculations to arrive at Pell’s equation. I want to boil it down here and just state that in this case we get that x = (3a+1)/2

Solving Pell’s equation

According to Wikipedia we have that

is a solution for . This can also be stated recursivly as

And from Problem 66 we know that the . So now we can find all solutions to the Pell equation we just need to plug it back in

Getting it back to the almost equilateral triangles

This is a rather simple substitution since we have that (3a +/-1)/2 = x  thus we get that

We can also find the area based on x and y

So once we find a solution to the Pell equation we can check if the area and the side a is integral. In the case it is then we have a solution to the problem. Since x and y are easy to find and they grow very rapidly this will be a much easier way to solve this problem than going through 600 million solutions to check if they worked out. In fact there are only 15 solutions of Pell’s equation such that the perimeter of the triangle is less than the given 1.000.000.000 so that gives us 30 solutions to check, or a factor of 20.000.000 less than brute force.

Implementing the solution

All we need to do now is to implement the formulas in C# and run the program to get the solution.  On thing to note is that we also need to check that our solution to a and the area are larger than zero. Otherwise we will find the solutions with sides (1,1,2) and (1,1,0) neither of then being a real solution to the problem. With that in mind here is the code

long x = 2;
long y = 1;
long limit = 1000000000;
long result = 0;

while(true){
    // b = a+1
    long aTimes3 = 2 * x - 1;
    long areaTimes3 = y * (x - 2);
    if (aTimes3 > limit) break;

    if (aTimes3 > 0 &&
        areaTimes3 > 0 &&
        aTimes3 % 3 == 0 &&
        areaTimes3 % 3 == 0) {

        long a = aTimes3 / 3;
        long area = areaTimes3 / 3;

        result += 3 * a + 1;
    }

    //b = a-1
    aTimes3 = 2 * x + 1;
    areaTimes3 = y * (x + 2);

    if (aTimes3 > 0 &&
        areaTimes3 > 0 &&
        aTimes3 % 3 == 0 &&
        areaTimes3 % 3 == 0) {

        long a = aTimes3 / 3;
        long area = areaTimes3 / 3;

        result += 3 * a - 1;
    }

    long nextx = 2 * x + y * 3;
    long nexty = y * 2 + x;

    x = nextx;
    y = nexty;
}

Running this gives us

The sum of perimiters is 518408346
Solution took 0,0018 ms

An execution time which warms my heart.

Wrapping up

We have solved this problem by rewriting the area to the form of Pell’s equation which have far fewer solutions. Once we had the solutions to Pell’s equations we could check if it was a solution to this problem as well.

The source code for the problem can be found here.

I do believe that this problems can be solved in other ways, but I am not sure exactly how. If you have solved it in another way, please let me know. I would be very interested in that. Comments, pointing out mistakes and so on is as always very welcome.

Today’s blog image is shared under the creative commons license by Anders Sandberg