Problem 94: Almost Equilateral Triangles

Mathematical Foundation

Theorem 1 (Heron’s formula for isosceles triangles). An isosceles triangle with sides $(a, a, b)$ has area

Proof. The semi-perimeter is $s = (2a + b)/2$. By Heron’s formula:

Lemma 1 (Case $b = a+1$: integrality condition). For the triangle $(a, a, a+1)$, the area is a positive integer if and only if $(3a+1)(a-1)$ is a perfect square (and a further divisibility condition holds).

Proof. Substituting $b = a+1$ into Theorem 1:

For $A$ to be a positive integer, we need $(3a+1)(a-1) = m^2$ for some positive integer $m$, giving $A = (a+1)m/4$, and we additionally require $4 \mid (a+1)m$. $\square$

Lemma 2 (Case $b = a-1$: integrality condition). For the triangle $(a, a, a-1)$, the area is a positive integer if and only if $(3a-1)(a+1)$ is a perfect square (with an analogous divisibility condition).

Proof. Substituting $b = a - 1$:

Theorem 2 (Reduction to Pell’s equation). Both integrality conditions reduce to the standard Pell equation $X^2 - 3Y^2 = 1$.

Proof. Case 1 ($b = a+1$): Set $(3a+1)(a-1) = m^2$. Multiplying out: $3a^2 - 2a - 1 = m^2$. Multiply by 3: $9a^2 - 6a - 3 = 3m^2$, whence $(3a-1)^2 - 3m^2 = 4$. Setting $X = (3a-1)/2$ and $Y = m/2$ (whose integrality we verify for valid solutions), we obtain $X^2 - 3Y^2 = 1$.

Case 2 ($b = a-1$): Set $(3a-1)(a+1) = m^2$. Then $3a^2 + 2a - 1 = m^2$, so $9a^2 + 6a - 3 = 3m^2$, giving $(3a+1)^2 - 3m^2 = 4$. Setting $X = (3a+1)/2$, $Y = m/2$ yields $X^2 - 3Y^2 = 1$. $\square$

Theorem 3 (Pell recurrence). The Pell equation $X^2 - 3Y^2 = 1$ has fundamental solution $(X_1, Y_1) = (2, 1)$. All positive solutions are generated by the linear recurrence

Proof. One verifies directly that $(2,1)$ is the smallest positive solution. The recurrence corresponds to multiplication in the ring $\mathbb{Z}[\sqrt{3}]$: $(X_k + Y_k\sqrt{3})(2 + \sqrt{3}) = (2X_k + 3Y_k) + (X_k + 2Y_k)\sqrt{3}$. The norm $N(X + Y\sqrt{3}) = X^2 - 3Y^2$ is multiplicative, so if $X_k^2 - 3Y_k^2 = 1$ and $2^2 - 3 \cdot 1^2 = 1$, then

All positive solutions arise this way by the theory of Pell equations (see, e.g., Niven, Zuckerman, and Montgomery, An Introduction to the Theory of Numbers, Theorem 7.26). $\square$

Theorem 4 (Recovery of triangle parameters). From each Pell solution $(X_k, Y_k)$:

• If $X_k \equiv 1 \pmod{3}$: Case 1 applies with $a = (2X_k + 1)/3$, perimeter $= 3a + 1$.
• If $X_k \equiv 2 \pmod{3}$: Case 2 applies with $a = (2X_k - 1)/3$, perimeter $= 3a - 1$.

Moreover, the residues alternate: $X_k \bmod 3 \in \{2, 1, 2, 1, \ldots\}$ for $k = 1, 2, 3, \ldots$, so every Pell solution yields exactly one valid triangle.

Proof. For Case 1: $X = (3a-1)/2$ gives $a = (2X+1)/3$, which is a positive integer if and only if $X \equiv 1 \pmod{3}$. For Case 2: $X = (3a+1)/2$ gives $a = (2X-1)/3$, requiring $X \equiv 2 \pmod{3}$.

For the alternation, we proceed by induction. Base: $X_1 = 2 \equiv 2 \pmod{3}$. Inductive step: $X_{k+1} = 2X_k + 3Y_k \equiv 2X_k \pmod{3}$. Since $2 \cdot 2 \equiv 1$ and $2 \cdot 1 \equiv 2 \pmod{3}$, the residues alternate. $\square$

Editorial

The hard part is not searching over side lengths directly, but recognizing that the integral-area condition turns both $a,a,a+1$ and $a,a,a-1$ into the same Pell-type recurrence. Once that reduction is done, the original geometric search space collapses to a simple sequence of Pell solutions.

Each Pell solution produces at most one almost-equilateral triangle, and the residue of $X$ modulo $3$ tells us which of the two cases we are in. So the algorithm generates candidates by walking through Pell solutions in increasing size, converts each one back into a perimeter, filters by the appropriate congruence case, and stops as soon as the perimeter limit is exceeded.

Pseudocode

Initialize the Pell solution to the fundamental pair $(2,1)$.
Set the perimeter sum to 0.

Repeat:
    Inspect the current Pell solution

    If it corresponds to the $a,a,a+1$ case:
        recover $a$ and the perimeter from that formula
    Otherwise:
        recover $a$ and the perimeter from the $a,a,a-1$ formula

    If the perimeter exceeds the limit, stop
    If the triangle is nondegenerate, add its perimeter to the total

    Advance to the next Pell solution using the linear recurrence

Return the accumulated perimeter sum.

Complexity Analysis

Time: Solutions to the Pell equation grow exponentially as $X_k \sim (2 + \sqrt{3})^k / 2$. The number of solutions with perimeter $\le L$ is $\Theta(\log L)$. Each iteration performs $O(1)$ arithmetic. Total: $O(\log L)$.

Space: $O(1)$ (two variables for the current Pell solution).

Answer

#include <bits/stdc++.h>
using namespace std;

int main() {
    // Almost equilateral triangles: sides (a, a, a+/-1) with integral area.
    // Both cases reduce to Pell equation X^2 - 3Y^2 = 1.
    // Fundamental solution: (X,Y) = (2,1).
    // Recurrence: X' = 2X + 3Y, Y' = X + 2Y.
    //
    // X mod 3 == 1 => Case 1: a = (2X+1)/3, perimeter = 3a+1
    // X mod 3 == 2 => Case 2: a = (2X-1)/3, perimeter = 3a-1

    const long long LIMIT = 1000000000LL;
    long long total = 0;
    long long x = 2, y = 1;

    while (true) {
        long long a, perim;
        if (x % 3 == 1) {
            a = (2 * x + 1) / 3;
            perim = 3 * a + 1;
        } else {
            a = (2 * x - 1) / 3;
            perim = 3 * a - 1;
        }
        if (perim > LIMIT) break;
        if (a >= 2) total += perim;

        long long nx = 2 * x + 3 * y;
        long long ny = x + 2 * y;
        x = nx;
        y = ny;
    }

    cout << total << endl;
    return 0;
}

"""
Project Euler Problem 94: Almost Equilateral Triangles

Find the sum of perimeters of all almost equilateral triangles (sides a,a,a+/-1)
with integral area and perimeter not exceeding 10^9.

Both cases reduce to the Pell equation X^2 - 3Y^2 = 1 with fundamental
solution (2,1) and recurrence X' = 2X + 3Y, Y' = X + 2Y.

Answer: 518408346
"""


def solve(limit=1_000_000_000):
    total = 0
    x, y = 2, 1  # fundamental Pell solution

    while True:
        if x % 3 == 1:
            # Case b = a+1: a = (2x+1)/3, perimeter = 3a+1
            a = (2 * x + 1) // 3
            perim = 3 * a + 1
            if perim > limit:
                break
            if a >= 2:
                total += perim
        else:
            # Case b = a-1: a = (2x-1)/3, perimeter = 3a-1
            a = (2 * x - 1) // 3
            perim = 3 * a - 1
            if perim > limit:
                break
            if a >= 2:
                total += perim

        x, y = 2 * x + 3 * y, x + 2 * y

    return total


if __name__ == "__main__":
    answer = solve()
    assert answer == 518408346
    print(answer)