Problem 138: Special Isosceles Triangles

Project Euler Problem 138 Solution

EulerSolve provides an optimized solution for Project Euler Problem 138, Special Isosceles Triangles, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary We seek isosceles triangles with equal sides $L$, base $b$, and altitude $h$ such that $h=b\pm1$. The triangles are ordered by increasing $L$, and the required result is the sum of the first twelve leg lengths. The altitude of an isosceles triangle bisects the base, so the geometry immediately becomes a right-triangle problem. The valid triangles do not need to be found by brute force; they form a Pell-type sequence, and the implementations use the resulting recurrence directly. Mathematical Approach Let $m=b/2$. Since $4L^2=4h^2+b^2$, the base must be even, so $m$ is an integer. Write the sign in the condition $h=b\pm1$ as $\sigma\in\{-1,+1\}$, which lets us express the height as $h=2m+\sigma$. From the Triangle to a Pell Equation Splitting the isosceles triangle along its altitude gives a right triangle with legs $m$ and $h$, and hypotenuse $L$. Therefore $$L^2=m^2+(2m+\sigma)^2=5m^2+4\sigma m+1.$$ Multiply by $5$ and complete the square: $$5L^2=25m^2+20\sigma m+5=(5m+2\sigma)^2+1.$$ If we define $$X=5m+2\sigma,$$ then every special isosceles triangle produces a solution of $$X^2-5L^2=-1.$$ So the geometric problem is equivalent to finding the positive nondegenerate solutions of the negative Pell equation $X^2-5Y^2=-1$, with $Y=L$. Recovering the Triangle from a Pell Solution The converse is just as important....

Detailed mathematical approach

Problem Summary

An isosceles triangle has two equal sides, the legs, of length $L$, and a third side, the base, of length $b$; its height $h$ is the distance from the apex to the base. For $b=16$ and $L=17$ the Pythagorean theorem gives $h=\sqrt{17^2-8^2}=15$, one less than the base, and $b=272$, $L=305$ give $h=273$, one more than the base; this is the second smallest isosceles triangle with $h=b\pm1$. We must find the sum of the legs $L$ of the twelve smallest isosceles triangles with $h=b\pm1$ in which $b$ and $L$ are positive integers. ^[1]

The whole solution in one sentence: cutting the triangle in half along its height gives a right triangle with legs $b/2$ and $b\pm1$, a little algebra turns this into the equation $X^2-5L^2=-1$, whose solutions all arise from the smallest one by one fixed rule, and as a result the legs are $17$, $305$, $5473$, and so on, each $18$ times the previous one minus the one before it, so we only have to add the first twelve of them.

Mathematical Approach

We reduce the problem to a right triangle, find the first triangles by a search, explain them with a Pell equation, prove by descent that the pattern misses no triangle, and turn it into a recurrence.

1. Half of the triangle

The height from the apex meets the base at its midpoint and cuts the triangle into two congruent right triangles, each with legs $b/2$ and $h$ and hypotenuse $L$. ^[2] By the Pythagorean theorem $(b/2)^2+h^2=L^2$. Write $h=b+\sigma$ with $\sigma=-1$ or $\sigma=+1$. Then $h$ is an integer, so $b^2/4=L^2-h^2$ is an integer as well, and since the square of an odd number is odd, $b$ is even. With $b=2m$, where the half-base $m$ is a positive integer, we get $h=2m+\sigma$ and

$$L^2=m^2+(2m+\sigma)^2=5m^2+4\sigma m+1.$$

Conversely, a positive integer $m$ and a sign $\sigma$ for which $5m^2+4\sigma m+1$ is a perfect square $L^2$ give a triangle with base $2m$, height $2m+\sigma$ and legs $L$. For the first triangle of the statement $m=8$ and $\sigma=-1$: $8^2+15^2=64+225=289=17^2$, and $(8,15,17)$ is a primitive Pythagorean triple, one whose entries have no common divisor greater than $1$. ^[3]

2. The first triangles by search

Testing every half-base $m\le10^6$ with both signs finds exactly five triangles:

$m=8$, $\sigma=-1$: $b=16$, $h=15$, $L=17$;
$m=136$, $\sigma=+1$: $b=272$, $h=273$, $L=305$;
$m=2448$, $\sigma=-1$: $b=4896$, $h=4895$, $L=5473$;
$m=43920$, $\sigma=+1$: $b=87840$, $h=87841$, $L=98209$;
$m=788120$, $\sigma=-1$: $b=1576240$, $h=1576239$, $L=1762289$.

Two patterns stand out. The sign alternates, and each leg is about $18$ times the previous one; more precisely, $18\cdot305-17=5473$, $18\cdot5473-305=98209$ and $18\cdot98209-5473=1762289$. A search like this cannot reach the twelfth triangle, whose half-base has $15$ digits. The next sections explain both patterns and prove that they never fail.

3. Completing the square

Multiplying $L^2=5m^2+4\sigma m+1$ by $5$ and using $\sigma^2=1$ gives

$$5L^2=25m^2+20\sigma m+5=(5m+2\sigma)^2+1.$$

So, with $X=5m+2\sigma$, every triangle gives a solution in positive integers of

$$X^2-5L^2=-1.$$

For a fixed positive integer $n$ that is not a perfect square, the equation $x^2-ny^2=-1$ in integers $x,y$ is called a negative Pell equation; for $n=5$ its smallest positive solution is $(2,1)$. ^[4] For the first triangle $X=40-2=38$, and indeed $38^2-5\cdot17^2=1444-1445=-1$.

4. From a solution back to a triangle

Conversely, let $X$ and $Y$ be positive integers with $X^2-5Y^2=-1$. Then $X^2=5Y^2-1$ leaves the remainder $4$ after division by $5$. The squares of numbers with the remainders $0,1,2,3,4$ leave the remainders $0,1,4,4,1$, so $X$ leaves the remainder $2$ or $3$. Put $\sigma=+1$ in the first case and $\sigma=-1$ in the second. In both cases $m=(X-2\sigma)/5$ is an integer with $X=5m+2\sigma$, and reading the computation of Section 3 backwards gives $Y^2=m^2+(2m+\sigma)^2$. So $Y$ is the leg of the triangle with half-base $m$, unless $m=0$. That happens only for $X=2$ and $Y=1$, a degenerate triangle with base $0$. The two constructions undo each other, so the triangles correspond one to one to the positive solutions of $X^2-5Y^2=-1$ other than $(2,1)$, with legs $L=Y$.

5. Every solution comes from $2+\sqrt5$

To find all solutions, we treat $x^2-5y^2=-1$ together with $x^2-5y^2=+1$ and look at the step

$$(x,y)\mapsto(2x+5y,\ x+2y).$$

Starting from $(1,0)$, it produces $(2,1)$, $(9,4)$, $(38,17)$, $(161,72)$ and $(682,305)$, and it flips the sign of $x^2-5y^2$, because $(2x+5y)^2-5(x+2y)^2=5y^2-x^2$. In the language of the number $\sqrt5$, the step multiplies $x+y\sqrt5$ by $2+\sqrt5$, since $(x+y\sqrt5)(2+\sqrt5)$${}=(2x+5y)+(x+2y)\sqrt5$. So the pair $(x_k,y_k)$ reached after $k$ steps satisfies $x_k+y_k\sqrt5=(2+\sqrt5)^k$.

Claim. Every pair of non-negative integers $(x,y)$ with $x^2-5y^2=\pm1$ is one of the pairs $(x_k,y_k)$, and $x_k^2-5y_k^2=(-1)^k$.

Proof. Take such a pair with $y\ge1$, let $e=x^2-5y^2$, and apply the reverse step $(x',y')=(5y-2x,\ x-2y)$. One checks that $2x'+5y'=x$ and $x'+2y'=y$, so the step leads from $(x',y')$ back to $(x,y)$, and therefore $x'^2-5y'^2=-e$. Three inequalities show that $(x',y')$ is again a pair of the same kind, with a smaller second entry:

$x^2-4y^2=y^2+e\ge0$, so $x\ge2y$ and $y'\ge0$;
$9y^2-x^2=4y^2-e\gt0$, so $x\lt3y$ and $y'\lt y$;
$25y^2-4x^2=5y^2-4e\gt0$, so $2x\lt5y$ and $x'\gt0$.

Repeating the reverse step, the second entry decreases strictly, so after finitely many steps it reaches $0$; this is the method of infinite descent. ^[5] A pair with $y=0$ has $x^2=\pm1$, so it is $(1,0)$, with the sign $+1$. Running the same steps forward leads from $(1,0)$ back to $(x,y)$, so $(x,y)=(x_k,y_k)$, where $k$ is the number of steps, and since every step flips the sign, $x^2-5y^2=(-1)^k$. For example, $(682,305)$ descends through $(161,72)$, $(38,17)$, $(9,4)$ and $(2,1)$ to $(1,0)$ in five steps, and indeed $682^2-5\cdot305^2$${}=465124-465125=-1$. $\square$

The solutions of $X^2-5Y^2=-1$ are therefore exactly the pairs with odd $k$. The step $k=1$ gives the degenerate $(2,1)$, so by Section 4 the triangles are the pairs with $k=3,5,7,\dots$. The pair $(9,4)$ with $k=2$ is the fundamental solution of $x^2-5y^2=1$, the one from which all solutions of that equation arise. ^[4]

6. Two steps at a time

The triangles use every second pair of the chain, so we combine two steps into one: $(x,y)\mapsto(9x+20y,\ 4x+9y)$, which multiplies by $(2+\sqrt5)^2=9+4\sqrt5$. Write $(X_n,L_n)$ for the pair with $k=2n+1$, so that $(X_0,L_0)=(2,1)$ and triangle number $n$ has legs of length $L_n$:

$$X_{n+1}=9X_n+20L_n,\qquad L_{n+1}=4X_n+9L_n.$$

The second equation gives $4X_n=L_{n+1}-9L_n$. Inserting this into $L_{n+2}=4X_{n+1}+9L_{n+1}$${}=36X_n+80L_n+9L_{n+1}$ eliminates $X$:

$$L_{n+2}=18L_{n+1}-L_n,\qquad L_1=17,\quad L_2=305.$$

This is a linear recurrence with constant coefficients: trying $L_n=r^n$ and dividing by $r^n$ gives its characteristic equation $r^2-18r+1=0$, with the roots $9\pm4\sqrt5$, and every solution combines the $n$-th powers of these two roots. ^[6] It holds for $n=0$ as well: $18\cdot17-1=305$. Both $L_n$ and $X_n$ increase, and $X_{n+1}-X_n=8X_n+20L_n$ exceeds $14$; since $2\sigma_n$ changes by at most $4$, the half-base $m_n=(X_n-2\sigma_n)/5$ grows by more than $2$, and the height $2m_n+\sigma_n$ grows too. So the order of the triangles is the same by legs, by base and by height, and the twelve smallest triangles are those with $n=1,\dots,12$. Finally, $X_{n+1}+X_n=10X_n+20L_n$ is a multiple of $5$, so the remainders $3$ and $2$ of $X_n$ alternate, starting with $X_1=38$: $h=b-1$ for odd $n$ and $h=b+1$ for even $n$, the first pattern of Section 2.

7. Worked example: the third triangle

Start from the second triangle of the statement, $(X_2,L_2)=(682,305)$. Since $682$ leaves the remainder $2$, we have $\sigma=+1$, $m=(682-2)/5=136$, $b=272$ and $h=273$, as in the statement. One double step gives

$$X_3=9\cdot682+20\cdot305=6138+6100=12238,$$

$$L_3=4\cdot682+9\cdot305=2728+2745=5473,$$

and the recurrence agrees: $18\cdot305-17=5473$. Now $12238^2-5\cdot5473^2$${}=149768644-149768645=-1$. The remainder of $12238$ is $3$, so $\sigma=-1$, $m=(12238+2)/5=2448$, $b=4896$ and $h=4895$, and $2448^2+4895^2=5992704+23961025$${}=29953729=5473^2$: this is the third triangle of Section 2.

8. Fibonacci numbers and growth

The legs are hidden in the Fibonacci numbers $F_0=0$, $F_1=1$, $F_{j+1}=F_j+F_{j-1}$. With the golden ratio $\varphi=(1+\sqrt5)/2$ and $\psi=(1-\sqrt5)/2$, Binet's formula states $F_j=(\varphi^j-\psi^j)/\sqrt5$. ^[7] Expanding $(1+\sqrt5)^3=16+8\sqrt5$ shows $\varphi^3=2+\sqrt5$, and in the same way $\psi^3=2-\sqrt5$. The step of Section 5 also turns $x-y\sqrt5$ into $(x-y\sqrt5)(2-\sqrt5)$, so $x_k-y_k\sqrt5=(2-\sqrt5)^k$. Subtracting this from $x_k+y_k\sqrt5=(2+\sqrt5)^k$ gives

$$\begin{aligned}y_k&=\frac{(2+\sqrt5)^k-(2-\sqrt5)^k}{2\sqrt5}\\&=\frac{\varphi^{3k}-\psi^{3k}}{2\sqrt5}=\frac{F_{3k}}{2},\end{aligned}$$

and with $k=2n+1$ triangle number $n$ has legs of length $L_n=F_{6n+3}/2$. For instance, $F_9=34$, $F_{15}=610$ and $F_{21}=10946$ give $17$, $305$ and $5473$. The On-Line Encyclopedia of Integer Sequences lists these numbers as A007805, with the recurrence of Section 6. ^[8]

The formula also shows how fast the legs grow. Since $0\lt\sqrt5-2\lt1/4$, the part of $L_n=y_{2n+1}$ that contains $(2-\sqrt5)^{2n+1}$ is smaller than $1/2$ in size, so $L_n$ is the integer nearest to $(2+\sqrt5)^{2n+1}/(2\sqrt5)$, and $L_{n+1}/L_n$ approaches $9+4\sqrt5\approx17.944$. Every further triangle makes the legs about $18$ times longer and adds about $\log_2 17.944\approx4.17$ binary digits.

9. A formula for the partial sums

The recurrence can also be summed. Written as $(L_{j+1}-L_j)-(L_j-L_{j-1})=16L_j$ and added up for $j=1,\dots,N$, all inner differences cancel:

$$(L_{N+1}-L_N)-(L_1-L_0)=16\,(L_1+L_2+\dots+L_N).$$

Since $L_1-L_0=16$, the sum of the first $N$ legs is $S_N=(L_{N+1}-L_N)/16-1$. For example, $S_1=(305-17)/16-1=17$, $S_2=(5473-305)/16-1=322$ and $S_3=(98209-5473)/16-1=5795$, which is $17+305+5473$. It serves as an independent check of the summing loop.

How the Code Works

The C++ program ^[9] uses only the recurrence of Section 6 and the legs $17$ and $305$ of the two triangles in the statement; it never forms $X$, $m$ or $h$. main reads the options with parse_arguments: --count=N sets the number of triangles, by default $12$, and parse_int_after_prefix accepts its value only as a nonempty string of decimal digits; --skip-checkpoints turns the check off. Any other argument, or a count below $1$, ends the program with exit code $1$. Then run_checkpoints requires solve(2) to be $322=17+305$, and the program ends with exit code $2$ otherwise; finally main prints solve(options.count).

solve computes in i64, an alias of std::int64_t. The variables a and b start at $L_1=17$ and $L_2=305$, and sum first receives $L_1$. Before the iteration with index i, which runs from $2$ to the count $N$, a holds $L_{i-1}$ and b holds $L_i$; the iteration adds b to sum, computes c = 18 * b - a, which is $L_{i+1}$ by Section 6, and moves the pair on. So sum ends as $S_N$, and the last iteration computes $L_{N+1}$, which is never added. The checkpoint solve(2) only adds the two starting values and never uses the term it computes, so it tests the summation, not the recurrence; the recurrence rests on the proof of Sections 5 and 6.

The Python function solve runs the same loop with count = 12 and the tuple assignment a, b = b, 18 * b - a; Python integers have unlimited precision. The Java main runs it with long variables and $12$ terms. Neither has options or checks. The header comment of the Python file writes the condition as $|b-2h|=1$, which does not fit the notation of the problem: the condition is $|h-b|=1$, that is, $|h-2m|=1$ for the half-base $m$.

For twelve triangles the largest value formed is $18L_{12}$, on the way to the unused $L_{13}$; it is below $2^{55}$, far from the limit $2^{63}-1$ of a signed 64-bit integer. ^[10] Every further triangle adds about $4.17$ binary digits, so the optional C++ count has a limit: --count=N is exact and free of overflow for $N\le14$. For $N=15$ the sum itself still fits, but the last iteration evaluates $18L_{15}\gt2^{66}$ for the unused $L_{16}$. This signed overflow is undefined behaviour in C++, so from $N=15$ on no output is guaranteed, and from $N=16$ on the true sum no longer fits in 64 bits. The digit loop of parse_int_after_prefix does not guard its int against overflow either. A Java long would wrap around silently, but there the count is fixed at $12$.

Complexity and Verification

For $N$ triangles the loop makes $N-1$ iterations with one multiplication, one subtraction and one addition each, on a constant number of variables; twelve triangles take $11$ iterations, and the C++ checkpoint solve(2) adds one more. With fixed-width integers this is $O(N)$ time and $O(1)$ memory. With Python's unbounded integers the $n$-th term has about $4.17n$ bits, and adding or multiplying by $18$ costs time proportional to the number of bits, so the work is $O(N^2)$ bit operations and the memory $O(N)$ bits, still negligible. A search over half-bases as in Section 2 would have to test about $5\cdot10^{14}$ of them to reach the twelfth triangle.

The only built-in check is the C++ checkpoint $S_2=322$; the Python and Java programs contain none. For this article we verified, separately from the published code:

a direct search over all half-bases $m\le10^9$ with both signs finds exactly seven triangles, with the legs $17$, $305$, $5473$, $98209$, $1762289$, $31622993$ and $567451585$, the first seven terms of the recurrence;
a search over all $y\le10^9$ finds exactly $16$ pairs of non-negative integers with $x^2-5y^2=\pm1$, the pairs $k=0,\dots,15$ of the chain of Section 5, with alternating signs;
for every $n\le40$, the double step gives $X_n^2-5L_n^2=-1$, the recurrence and $L_n=F_{6n+3}/2$ hold, the remainders of $X_n$ alternate, and $m=(X_n-2\sigma_n)/5$ gives a triangle with $h=b\pm1$; the partial-sum formula of Section 9 holds for every $N\lt40$;
the three programs print the same value, equal to the sum of the first twelve terms of the recurrence computed separately in Python; the C++ program was built with Clang and GCC, and a build with -fsanitize=undefined reports no error in the default run but reports the overflow for --count=15.

Footnotes and References

The references below supply the background facts used above. The reduction to the Pell equation, the descent proof that the chain contains every solution, the recurrence, the partial-sum formula and the integer-size limits are derived explicitly in this article.

Project Euler 138 — Special Isosceles Triangles. The official statement gives the triangles with b = 16, L = 17, h = 15 and with b = 272, L = 305, h = 273, the two smallest with h = b ± 1, and asks for the sum of L over the twelve smallest such triangles in which b and L are positive integers.
Wikipedia — Isosceles triangle. The altitude to the base bisects the base and splits the triangle into two congruent right triangles, so a triangle with legs a and base b has the height h = √(a² − b²/4).
Wikipedia — Pythagorean triple. A Pythagorean triple consists of positive integers a, b, c with a² + b² = c²; the article lists (8, 15, 17) among the 16 primitive triples with entries up to 100.
Wikipedia — Pell's equation. Its tables give (2, 1) as the smallest solution of the negative equation x² − 5y² = −1 and (9, 4) as the fundamental solution of x² − 5y² = 1, which squaring the negative solution yields; all solutions of x² − ny² = 1 are powers of the fundamental solution.
Wikipedia — Proof by infinite descent. The method rests on the well-ordering principle: there cannot be an infinite sequence of ever smaller natural numbers. Fermat often used it for Diophantine equations.
Wikipedia — Linear recurrence with constant coefficients. For aₙ = A·aₙ₋₁ + B·aₙ₋₂ the characteristic equation is r² − Ar − B = 0; with distinct roots λ₁, λ₂ the solutions are aₙ = Cλ₁ⁿ + Dλ₂ⁿ.
Wikipedia — Fibonacci sequence. With F₀ = 0 and F₁ = 1, Binet's formula Fₙ = (φⁿ − ψⁿ)/√5 holds, where φ = (1 + √5)/2 is the golden ratio and ψ = (1 − √5)/2.
OEIS A007805 — a(n) = Fibonacci(6n + 3)/2. The sequence 1, 17, 305, 5473, … satisfies a(n) = 18a(n − 1) − a(n − 2). The entry notes that X = 2·A049629(n) and Y = a(n), for n ≥ 0, give all positive solutions of X² − 5Y² = −1, and that a(n) is the hypotenuse of the Pythagorean triples (u, v, w) with |2u − v| = 1; for this the degenerate a(0) = 1 of Section 4 is left out.
C++ — Euler138.cpp. The linked immutable revision contains parse_int_after_prefix, parse_arguments, solve and run_checkpoints. It is the implementation record for this article.
Integer arithmetic: by the C++ working draft, [expr.pre], an arithmetic result that is not representable in its type is undefined behaviour; by the Java Language Specification, §4.2.1–4.2.2, a long lies between −2⁶³ and 2⁶³ − 1 and the integer operators do not indicate overflow in any way; by the Python documentation, integers have unlimited precision.

Problem 138 source code

C++

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <string>

namespace {

using i64 = std::int64_t;

struct Options {
    int count = 12;
    bool run_checkpoints = true;
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }

    int parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_int_after_prefix(arg, "--count=", options.count)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return options.count >= 1;
}

i64 solve(const int count) {
    i64 sum = 0;

    i64 a = 17;
    i64 b = 305;

    if (count >= 1) {
        sum += a;
    }
    for (int i = 2; i <= count; ++i) {
        sum += b;
        const i64 c = 18 * b - a;
        a = b;
        b = c;
    }

    return sum;
}

bool run_checkpoints() {
    if (solve(2) != 322) {
        std::cerr << "Checkpoint failed for first two terms" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    std::cout << solve(options.count) << '\n';
    return 0;
}

Python

# Problem 138: Special isosceles triangles
# Sum of first 12 L values where |b - 2h| = 1 in isosceles triangle.
# Recurrence: L_n = 18*L_{n-1} - L_{n-2}, seeds L_1=17, L_2=305.

def solve():
    count = 12
    a, b = 17, 305
    total = a
    for i in range(2, count + 1):
        total += b
        a, b = b, 18 * b - a
    print(total)

solve()

Java

public class Euler138 {
    public static void main(String[] args) {
        int count = 12;
        long a = 17, b = 305, sum = a;
        for (int i = 2; i <= count; i++) {
            sum += b;
            long c = 18 * b - a;
            a = b;
            b = c;
        }
        System.out.println(sum);
    }
}