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 analmost equilateral triangleto 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 allalmost equilateral triangleswith 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

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 🙁

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.

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

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.

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

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

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)

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 :).

Thank you 🙂

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 ?

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.

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.

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.

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?

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.

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.

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

Re: using Herons rule, A = sqrt((p *(p-a)* p-b)*(p-c))) where p is a+b+c/2

Since a = b, you can rewrite as

A = (p-a) * sqrt(p * (p-c))

This limits the required precision of the sqrt operation to half as many digits of precision, though you still about 20 digits of precision (IIRC) to avoid false positives and all you need to know is if the square root is an integer. Using standard double precision math, you do get a handful of false positives using the refactored area formula.

Of course, you can also reject false positives by back-substituting the calculated square root to see if the math is exact.

Certainly not as elegant or as nearly as fast as using the Pell method, but it kind of bothered me that you thought it was impossible to use for this problem since I solved it this way first myself using the refactored area formula. A simple brute force approach makes a great double check.

a = 92604733, b = 92604734

h = sqrt( (a * a) – (b/2 * b/2) ) = 80198051

a, b, h are all integer. difference of a and b is 1.

I want to know why this triangle is not almost equilateral triangle.

Hi kyduke

Some calculations and results from your comment

(a * a) = 92604733*92604733 = 8575636574001289;

(b/2 * b/2) => [92604734/2 = 46302367]; 46302367*46302367 = 2143909189802689;

8575636574001289 – 2143909189802689 = 6431727384198600;

Note :

sqrt (6431727384198600) = 80198051,0000001 … (digital number)

80198051^2=6431727384198601

___

Sources :

1) Big Integer Calculator

http://www.javascripter.net/math/calculators/100digitbigintcalculator.htm

2) Microsoft Algorithm : Square Root via C#

BigInteger.Log Method (BigInteger)

https://msdn.microsoft.com/en-us/library/dd268263(v=vs.110).aspx

@hyduke

Further calculations and results from your comment.

(a* a) = 92604733*92604733 = 8575636574001289;

(b/2 * b/2) => [92604734/2 = 46302367]; 46302367*46302367 = 2143909189802689;

8575636574001289 – 2143909189802689 = 6431727384198600;

More details

h^2 = 6431727384198600

sqrt (6431727384198600) = 80198050.99999999…

(80198050.99999999)^2 = 6431727384198599.396039

(80198050.999999999)^2 = 6431727384198600.839604

(re: 6431727384198600)

So, sqrt (6431727384198600) is an irrational number.

___

Source:

keisan Online Calculator

http://keisan.casio.com/calculator

______

Note :

The output from code (1) reported in my previous comment is confusing.

(probably overflow error) :

Quote :

« sqrt (6431727384198600) = 80198051,0000001 »

It is evident that the sqrt of (6431727384198600) will be smaller than the sqrt of (6431727384198601)

___

Source:

1) Microsoft Algorithm : Square Root via C#

BigInteger.Log Method (BigInteger)

https://msdn.microsoft.com/en-us/library/dd268263(v=vs.110).aspx

hey kyduke

did you ever get an answer for this?

I get the same value plus som eother oens which apparently are not meant to be almost equilateral triangle equilateral triangles.

Little mistake in the code. It should be 5,5,6, not 5,5,4. The result calculation is correct in the end, because you make the mistake an even number of times it seems 🙂

Wanting to spend more time on other types of problems, I solved this one using Herons and a brute force approach looping over all 1 billion perimeters using quad float precision in the c language. Needless to say it was slow, but at least was done in under about a coffee break on my 5 year old budget machine.

But it’s brute force nature and no inter-dependence would probably have scaled very nicely with multi-threaded CPU or GPU or even a heterogeneous cluster.

_______

Well.. at least I learned a bit about high precision routines. That’s always useful! It’s really cool how these Euler challenges force you to learn lots of useful stuff. Either practical or algorithmic or mathematic.