Project Euler 138: Special isosceles triangles

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); } [/csharp] 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.

Posted by Kristian

9 comments

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

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.

Jean-Marie Hachey

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)

Jean-Marie Hachey

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/

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

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.

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.

Jean-Marie Hachey

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

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 Reply