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

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

Written by on 28 April 2012

Topics: Project Euler

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 perimeters 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

17 Comments For This Post I'd Love to Hear Yours!

  1. jacky says:

    Hi!
    I’ve tried to solve it using Heron’s formula, but I failed because I couldn’t make high-precision calculations on C#. If the area is X.00000Y, I got it as an integer X, so I got lots of wrong answers :(

  2. Kristian says:

    Yes that is in general a really big risk when you use floating point operations. You will get numerical errors. For some problems you can scale your way out of it. However, I would doubt that it is possible for this specific problem.

  3. lumingqd says:

    it seems your reasoning requires (3a-1)/2 and h are integers which are not proved, did I miss something? thanks.

  4. Kristian says:

    Yes that is correct that I assumed that, and I didn’t prove it. So let us do it here.

    A, a and b are all integrals from the problem description. So if b is even then a is odd.

    And that gives us . From this is follows that is integral and h is either integral or an irrational number.

    Furthermore we have that A = bh/2, or h = 2A/b. And since both A and b are integrals. We have that h is a rational number. So based on the 2 argumentations we can conclude that h must be integral if b is even.

    Furthermore since b is even then a is odd and that makes the 3a an odd number, so 3a-1 is even, and thus when divided by 2 it is still integral.

    If b is odd then we have that A = bh/2, and in order for A to be integral h must be integral and even. Otherwise it does not hold.

    However (3a-1)/2 is indeed to integral. However, based then the square of it must be integral since both other terms are integral.

    So that just leads us to conclude that b must be even, otherwise we have a contradiction.

  5. lumingqd says:

    Thank you very much for clear things up. It was a beautiful proof.

  6. Kristian says:

    Thank you for the question. It made me think long and hard about why it had to be so.

  7. Jean-Marie Hachey says:

    Table 1
    The first twelve almost equilateral triangles with integral sides, heights and surface areas.
    [Re: Project Euler 94: Investigating almost equilateral triangles with integral sides and area.]

    http://img4.hostingpics.net/pics/614280pe94tab1.jpg

    Table 1 shows that the first triangle has a perimeter of 16,
    while we obtain 14 with the algo (1). Obviously, the same
    situation is repeated for all triangles whose sides a and b
    are specifically one unit lower than their base c.

    Unless otherwise stated, all calculations were done with
    Microsoft Excel (3).

    ___

    Sources:
    1) Project Euler 94
    Kristian’s algorithm
    http://www.mathblog.dk/project-euler-94-almost-equilateral-triangles/
    2) Microsoft Visual C# 2010 Express
    3) Microsoft Office Excel (2007)

  8. Robert Watkins says:

    Brilliant approach. I solved it with Berggren’s Pythogorean triple generator. Compared to your use of Pell’s equation, it seems like brute force but the math is much simpler :).

  9. Gagan says:

    Hi,

    I am terribly confused with this. No, not with your solution, but my understanding that I developed while reading about this. Here it goes:

    The problem asks about Heronian isosceles triangles, right ? (Integral sides and integral area).

    Now as per the wiki: http://en.wikipedia.org/wiki/Integer_triangle#Isosceles_Heronian_triangles

    All isosceles heronian triangles satisfy those equations (please see he wiki). If we solve the euations, we get u^2 – 3*v^2 = 1 for b > a and
    and 3v^2 – u^2 = 1 for a > b.

    Now the second equation is a negative Pell’s equation which is not solvable for the coefficient 3. So how do we get triangles with a > b ?

    I am clueless where my understanding is going wrong.

    Any help ?

  10. Kristian says:

    I arrive at the same conclusion as you do. I can also see for the case of b > a, you arrive at the same Pell’s equation as I do in the blog post. But for the other case it differs.

  11. Ankeet says:

    Hey,
    I looked at your answer (after days of frustration of not getting the right one myself), and noticed that it is quite odd. Shouldn’t the answer be closer to 1 billion? The prompt asks for the sum of the perimeters of each triangle such that the sum does not exceed one billion. So why isn’t the answer much higher? My algorithm keeps getting 996784416.

  12. Kristian says:

    The obvious answer is that because all the triangles that match the criteria are apparantly rather small. The more profound answer I have no clue about.

  13. def says:

    Your code gives the result 7876380 which is not correct. Where 518408346 came from? A little bit of debugging shows that you are counting such values like (5,5,4) which is wrong. Might it be that you somehow made a mistake?

  14. Larry C says:

    I took a different approach that boiled down to an interactive dynamic programming style solution of sorts.

    The area of an isosceles triangle is (b/4)(4a^2-b^2)^0.5 where b is the length of the base and a is the length of the two equal sides.

    In the problem b = a+1 or a-1. So I asked it I know value a which provides a solution what is the next solution likely to look like. Since the square root in the equation for the area must be an integer the only way this is going to happen is if the next larger triangle is roughly twice the size of the previous one. But with the division by four in the equation the next larger actually needs to be on the order of four times as large to also get the integer area. I did not expect an exact ration of four due to how the a+1 and a-1 come into play. But it told me where to look for a pattern.

    So I located by brute force the first several solutions. I looked at the ratio of the size of the triangles. It came out in the range of a ratio of 3.7320 to 3.7325. It number is not fixed and oscillated due to the a+1 and a-1 component of the question. So locating the next larger triangle invoked a simple brute force search in the range of 3.7320 to 3.7325 time the previous triangle dimensions. That significantly reduced number of possibilities that needed to be considered.

  15. jeras says:

    Hmm, interesting. I would not have thought to solve it that way. Given the requirement of integral side lengths and area, I immediately thought of right triangles and pythagorean triples; in order for both the side lengths and area to be integral, you would need to have two right triangles with integral side lengths back to back. And of course the 5-5-6 almost equilateral example is simply two 3-4-5 right triangles back to back along the 4 side.

    So we need to find pythagorean triples (a, b, c) with a < b < c and abs(2a – c) = 1 or abs(2b – c) = 1 (although it turns out the second condition is never true when arranging a < b < c). If you follow the parent-child relationships for the tree of pythagorean triples, each time only one of the 3 children will have abs(2a – c) = 1. If the parent has 2a – c = 1, then the child will have -2a + c = 1 (or vice versa) when you expand the formulae for the child triple. And the perimeter of the resulting almost equilateral, then, is 2(a + c).

    The python code is very brief and runs in 15 usec.

    #! /usr/bin/env python
    
    import itertools as it
    
    def almost_equilaterals():
        a, b, c = 3, 4, 5
        while True:
            # assert abs(2*a - c) == 1
            yield 2*(a+c)
            a, b, c = -2*a+b+2*c, -a+2*b+2*c, -2*a+2*b+3*c
    
    def solve(limit=10**9):
        return sum(it.takewhile(lambda perim: perim &lt; limit,
                                almost_equilaterals()))
    
    if __name__ == '__main__':
        print solve()
    
  16. nuri says:

    woah! after finding solution using brute force, I tried jeras’ method (in c++)
    it gave me:
    sum 518408346
    elapsed 0.000033 ms
    damn that’s fast
    timer’s resolution is 1 ms so I had to repeat the method 1000000 times to measure it

Trackbacks For This Post

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

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

Notify me of comments via e-mail. You can also subscribe without commenting.