If a triangle has integral sides and length of two sides are 2014 and 2015

A brute force approach could enumerate triangles with integral edge lengths in order of increasing perimeter. In other words, examine partitions of increasingly larger numbers into three summands, taking the triangle inequality into account. What we'd need is some easy approach to detect this $A=2B$ condition. From the law of cosines, we get

$$\cos A=\frac{-a^2+b^2+c^2}{2bc}\qquad \cos B=\frac{a^2-b^2+c^2}{2ac}$$

We also know that $\cos A=\cos(2B)=2\cos^2B-1$ so we obtain the equation

$$ \frac{-2a^2+b^2+c^2}{2bc}=2\left(\frac{a^2-b^2+c^2}{2ac}\right)^2-1 \\ -a^4c + a^2b^2c + a^2c^3 = a^4b - 2a^2b^3 + b^5 - 2b^3c^2 + bc^4 \\ a^4b - 2a^2b^3 + b^5 + a^4c - a^2b^2c - 2b^3c^2 - a^2c^3 + bc^4 = 0 \\ (b + c)(-a - b + c)(a - b + c)(-a^2 + b^2 + bc) = 0 $$

The first factor would cannot be satisfied for positive edge lengths. The second translates to $c=a+b$ which would be a degenerate triangle. Likewise the third, $b=a+c$. So the only condition which remains is

$$a^2-b^2-bc=0\tag{1}$$

Now do a bit of enumeration, in order of increasing perimeter, and you find the following combination which satisfies both this and the triangle inequality:

$$a=15\qquad b=9\qquad c=16$$

However, the resulting triangle is not obtuse. So let's add a condition for that:

$$a^2+b^2<c^2$$

Now you get the solution

$$a=28\qquad b=16\qquad c=33$$

If you want to avoid the brute force enumeration, start with this reformulation of $\text{(1)}$:

$$c=\frac{a^2-b^2}{b}\in\mathbb N$$

So $a^2$ must be a multiple of $b$. On the other hand, $a$ itself cannot be a multiple of $b$ because otherwise, $bc$ would also be a multiple of $b^2$ so $c$ would be a multiple of $b$, and you could divide all lengths by $b$ to obtain a smaller solution. So for some $s,t,u\in\mathbb N$ you have

$$a=stu\qquad b=s^2u\qquad c=\frac{s^2t^2u^2-s^4u^2}{s^2u}=(t^2-s^2)u$$

You can see that $u=1$ is required for minimality, otherwise you could again divide all lengths by $u$. So $b=s^2=\gcd(a,b)^2$ is a square number.

The triangle inequality states

\begin{gather*} c=t^2-s^2<st+s^2=a+b \\ t^2-st-2s^2<0 \\ -s<t<2s \tag2 \end{gather*}

An obtuse angle at $c$ turns into

\begin{gather*} a^2+b^2=s^2t^2+s^4<t^4-2t^2s^2+s^4=(t^2-s^2)^2=c^2\\ 3s^2t^2<t^4 \\ 3s^2<t^2 \\ \sqrt3s<t \tag3 \end{gather*}

Taking $\text{(2)}$ and $\text{(3)}$ together, you get $\sqrt3s<t<2s$ which you can turn into the condition $\sqrt3s<2s-1$ since $t$, being an integer, must be at least one smaller than $s$. This in turn becomes $s>\frac1{2-\sqrt3}\approx3.7$ so $s=4$ is the first case where both conditions can be satisfied. You get

$$6.9\approx4\sqrt3<t<8$$

This can be satisfied by $t=7$, leading the result above:

$$a=st=4\cdot7=28\qquad b=s^2=4^2=16\qquad c=t^2-s^2=7^2-4^2=33$$

Larger $s$ lead to larger minimal values for $t$ which together lead to larger perimeter. Therefore the above solution is indeed minimal.

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

Running this gives us

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

• Project Euler 138: Special isosceles triangles

• Project Euler 139: Pythagorean tiles