Almost Equilateral Triangles

It is easily proved that no equilateral triangle exists with integral length sides and integral area. However, the almost equilateral triangle $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$).

This problem is named after the mathematician and programmer, Project Euler (Problem 94). The solution to this problem requires an understanding of elementary number theory, Heron’s formula for the area of a triangle, and Pell’s equation in number theory.

We shall first define the Heron’s formula for the area of a triangle. The formula is given by √(s(s – a)(s – b)(s – c)), where s is the semi-perimeter of the triangle (i.e., (a + b + c)/2), and a, b, and c are the sides of the triangle.

For an almost equilateral triangle with sides of length x, x, and x + 1, Heron’s formula gives us the area:

A = √((3x + 1)/2 * (x – 1)/2 * (x – 1)/2 * (x + 1)/2)
=> A = √(3x^2 – 1)/16 * x/2
=> A = (x * √(3x^2 – 1))/4
=> A = √((x^2) (3x^2 – 1)/16)

Similar Heron’s formula can also be written for an almost equilateral triangle with sides of length x, x, and x – 1 as:

A = √((3x – 1) * (x + 1) * (x + 1) * (x – 1))/16
=> A = (x * √(x^2 – 3))/4
=> A = √((x^2) (x^2 – 3)/16)

For the area to be an integer, the number under the square root sign must be a perfect square. So, we need (x^2) (3x^2 – 1) for the first case and (x^2)(x^2 – 3) for the second case to be perfect squares.

If we set (3x^2 – 1) = y^2, we get a Pell’s equation, a special type of Diophantine equation which says x^2 – 3y^2 = 1. Another similar Pell’s equation can also be formulated from the second case.

Pell’s equation can typically be solved using continued fractions or formulas for solving Diophantine equations. However, this problem asks not for the solution to the Pell’s equation, but rather the sum of the perimeters of such triangles.

So for computational efficiency, we use a recursive solution that generates successive Pythagorean triplets from a primitive one. Let (x, y) be a solution to 3x^2 − y^2 = 1. Then (2x + 3y, 2y + x) also satisfies the same equation. We can use this principle to find further solutions starting from (2, 1).

Computation shows that the solution for (x, y) under 1 billion is {(2, 1), (5, 3), (34, 20), (9801 5778) …}.

Summing the perimeters of these triangles (3x + 1 or 3x – 1), we get the answer, which is 518408346.

More Answers: