Project Euler 138: Special isosceles triangles

Project Euler 138: Special isosceles triangles

Written by on 2 March 2013

Topics: Project Euler

Problem 138 of Project Euler reads

Consider the isosceles triangle with base length, b = 16, and legs, L = 17.

By using the Pythagorean theorem it can be seen that the height of the triangle, h = √(172 – 82) = 15, which is one less than the base length.

With b = 272 and L = 305, we get h = 273, which is one more than the base length, and this is the second smallest isosceles triangle with the property that h = b ± 1.

Find ∑ L for the twelve smallest isosceles triangles for which h = b ± 1 and b, L are positive integers.

The key to solving this problem is definitively to only consider the rightangled part of the triangle, such that you get a triangle consisting of  one of the sides with length L, h and half the base (which I will denote x).

I started out by figuring out that solutions would be primitive pythagorean triplets which we have worked with in Problem 9  among other places. So I tried to build a solution where I check to see if the triplets fulfill the condition that 2x ± 1 = h. However, I quickly ran into the fact that the solution would take forever to complete. So I had to take a step back and try another approach.

So I started with writing what I knew about the problem. We have two equations

We can then use the second equation to substitute into the first and we get

Expanding the parenthesis gives us

Which can be shortened to

With the experience we have from solving previous Project Euler problems such as Problem 66 and Problem 94 (which I now realize is very similar) we should recognize that an equation of this form with integer solutions is a quadratic Diophantine equation, in fact this specific form is a Pell’s equation, and we should hit over to Dario Alpern’s Generic Two integer variable  equation solver which we visited in Problem 100.

Plugging in the numbers for the positive version gives us the solution that

We can directly implement this and get a solution. One thing that I noticed is that this gives alternating positive and negative solutions. Investigating the negative version of the original equation gives us the same sequence with the opposite sign. So the easiest was to just pick one and ignore the signs. Which means we can implement a solution as

long result = 0;

long x = 0;
long y = -1;

for (int i = 0; i < 12; i++) {
    long xnew = -9 * x + -4 * y + 4;
    long ynew = -20 * x + -9 * y + 8;

    x = xnew;
    y = ynew;

    result += Math.Abs(y);
}

This piece of code will run in much less than a millisecond and provide the correct solution, which is nice.

Wrapping up

You can as always find the full source code here.

Mike over at Dreamshire realized that the solution is related to the Fibonanacci sequence, in the sense that it starts at being half the ninth Fibonacci number and then continues as the half of increments of six. Such that the nth triangle has L = Fib(6n+3) for n=1,2,… I have included a codeup of that in the source code as well.

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

  1. Alex says:

    Hi,

    Unless I made some mistake implementing Fibonacci – Pell & Fibonacci solutions produces different results:

    Fibonacci solution timing: 0 mks
    Pell solution timing: 0 mks
    Pell: 1118049290473932
    Fibonacci: 1118049290473924

    Above it the result of executing my C++ implementation of the same algorithm.
    By the way, results of executing of your code are similar:

    Sum of first 12 L : 1118049290473932
    Solution took 0.0057 ms
    Sum of first 12 L : 1118049290473934
    Solution took 0.1133 ms

    Best regards,
    Alex

  2. Kristian says:

    Hi ALex

    You are right that they don’t give the same solution. It seems that the last entry in the Fibonacci version is 2 higher than it should be. Which is most likely a result of the implementation of the Fibonacci calculation. I will have to look a bit more into that.

  3. Jean-Marie Hachey says:

    Table 1
    Sum of cumulative and specific L
    [Re: Project Euler 138: Special isosceles triangles]

    http://img29.imageshack.us/img29/7505/pe138tablone.jpg

    ___

    Sources

    1) Project Euler 138
    Kristian’s algorithm
    http://www.mathblog.dk/files/euler/Problem138.cs
    2) Microsoft Visual C# 2010 Express
    3) Big Integer Calculator
    http://www.javascripter.net/math/calculators/100digitbigintcalculator.htm
    4) Microsoft Office Excel (2007)

  4. Jean-Marie Hachey says:

    Table 2
    Quadratic equations and isosceles triangles with h = b +- 1
    Re: Project Euler 138: Special isosceles triangles

    http://img12.imageshack.us/img12/175/pe138tabltwo.jpg

    ___

    Sources

    As cited above.

    Additional reference :
    Quadratic Formula Calculator
    http://quadratic-formula-calculator.com/

  5. wisosonic says:

    Hi all,

    I have the same steps as you until : \displaystyle 5x^2 \pm4x 1 = L^2

    and I dont know how did you get the other relations. I did exactly the same steps as the problem 94 :

    L^2 = H^2 + X^2
    L^2 = (2X +- 1)^2 + X^2
    L^2 = 4X^2 +- 4X + 1 + X^2
    L^2 = 5X^2 +- 4X + 1

    1)
    L^2 = 5x^2 + 4x + 1
    5L^2 = 25x^2 + 20x + 5
    5L^2 = (5x + 2)^2 + 1
    (5x + 2)^2 – 5L^2 = -1

    A^2 -5B^2 = -1

    2) …

    my question is : if we solve this equation we will get interger solutions. How to be sure that x = (A – 2)/5 is rational ? Or maybe I did something wrong or I should go in other way to solve
    L^2 = 5X^2 +- 4X + 1

    Thank you

  6. Kristian says:

    I am not completly sure I understand your question here. Are you sure you mean rational? Because if A is rational then x will be so too. If you mean integer then you can only be sure if you solve it as a diophantine equation.

  7. DiZ says:

    To link with Fibonacci sequence:
    One way to solve problem 136 (Fibonacci golden nuggets) is to solve this Diophantine equation: 5n^2 + 2n + 1 = K^2, very close to the one in this problem.
    By the way, those 2 equations lead to golden ration, used in Fibonacci sequence generation.

  8. Jean-Marie Hachey says:

    In my comment above: (March 10, 2013 at 12:54):
    Table 1
    Sum of cumulative and specific L
    [Re: Project Euler 138: Special isosceles triangles]

    This link (unavailable):
    http://img29.imageshack.us/img29/7505/pe138tablone.jpg
    has been replaced by :
    http://img4.hostingpics.net/pics/430180PE138tableone.jpg

    ___

    In my comment above: (March 13, 2013 at 12:33):
    Table 2
    Quadratic equations and isosceles triangles with h = b +- 1
    [Re: Project Euler 138: Special isosceles triangles]

    This link (unavailable):
    http://img12.imageshack.us/img12/175/pe138tabltwo.jpg
    has been replaced by :
    http://img4.hostingpics.net/pics/294163PE138tabletwo.jpg

  9. Tom says:

    How do you factor in the +- in the problem?

    It seems you’re only using the coefficients for h = b + 1.

    For h = b – 1 you get K = 4, L = 8.

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=""> <s> <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

This site uses cookies.