Project Euler

Integer Ladders

Two ladders of integer lengths x and y lean against opposite walls of a narrow street, crossing at height h. All four values x, y, h, and the street width w must be positive integers. For 0 < x < y...

Source sync Apr 19, 2026

Problem #0309

Level Level 15

Solved By 974

Languages C++, Python

Answer 210139

Length 391 words

number_theorymodular_arithmeticbrute_force

In the classic "Crossing Ladders" problem, we are given the lengths \(x\) and \(y\) of two ladders resting on the opposite walls of a narrow, level street. We are also given the height \(h\) above the street where the two ladders cross and we are asked to find the width of the street (\(w\)).

Here, we are only concerned with instances where all four variables are positive integers.

For example, if \(x = 70\), \(y = 119\) and \(h = 30\), we can calculate that \(w = 56\).

In fact, for integer values \(x\), \(y\), \(h\) and \(0 < x < y < 200\), there are only five triplets \((x, y, h)\) producing integer solutions for \(w\): \((70, 119, 30)\), \((74, 182, 21)\), \((87, 105, 35)\), \((100, 116, 35)\) and \((119, 175, 40)\).

For integer values \(x, y, h\) and \(0 < x < y < \num {1000000}\), how many triplets \((x, y, h)\) procedure integer solutions for \(w\)?

Problem 309: Integer Ladders

Mathematical Analysis

Geometric Relations

Let ladder x reach height p on one wall, and ladder y reach height q on the other:

x^2 = w^2 + p^2
y^2 = w^2 + q^2

By similar triangles, the crossing height satisfies:

h = \frac{pq}{p+q}

Pythagorean Triple Condition

Both (w, p, x) and (w, q, y) must be Pythagorean triples. We generate all primitive triples (m^2 - n^2, 2mn, m^2 + n^2) with m > n > 0, gcd(m,n) = 1, m-n odd, and their multiples, subject to hypotenuse < 1,000,000.

Integer Height Condition

Theorem. Let g = gcd(p, q), p = galpha, q = gbeta with gcd(alpha, beta) = 1. Then h is an integer if and only if (alpha + beta) | g.

Proof. We have h = galphabeta/(alpha + beta). Since gcd(alpha, beta) = 1, it follows that gcd(alpha*beta, alpha + beta) = 1 (as any prime dividing alpha + beta and alpha must divide beta, contradicting coprimality). Therefore h is an integer iff (alpha + beta) divides g.

Editorial

Two ladders of integer lengths x, y lean against opposite walls of an alley of integer width w, crossing at integer height h. x^2 = w^2 + p^2, y^2 = w^2 + q^2, h = pq/(p+q). Count (x, y, h) triplets with 0 < x < y < 1000000. For h to be integer: let g=gcd(p,q), p=galpha, q=gbeta, gcd(alpha,beta)=1. Then h = galphabeta/(alpha+beta), integer iff (alpha+beta) | g. We iterate over each hypotenuse value < 1,000,000, generate all Pythagorean triples. We then group triples by their shared leg w. Finally, iterate over each w with at least 2 triples, check all pairs (p1, x1), (p2, x2) with x1 != x2.

Pseudocode

For each hypotenuse value < 1,000,000, generate all Pythagorean triples
Group triples by their shared leg w
For each w with at least 2 triples, check all pairs (p1, x1), (p2, x2) with x1 != x2
For each pair, test the integer height condition

Complexity

Time: O(L * sqrt(L)) for triple generation where L = 10^6, plus pair checking
Space: O(L) for storing triples grouped by w

Answer

\boxed{210139}

C++ project_euler/problem_309/solution.cpp

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

int main() {
    // Integer Ladders
    // Two ladders of lengths x, y lean against opposite walls of alley width w.
    // x^2 = w^2 + p^2, y^2 = w^2 + q^2. Crossing height h = pq/(p+q) integer.
    // Count (x,y,h) with 0 < x < y < 1000000, all integers.
    //
    // Strategy: for each w, find all Pythagorean triples (w, p, hyp) with hyp < LIMIT.
    // For each pair of such triples sharing the same w, check if h is integer.

    const long long LIMIT = 1000000;

    // For each w, store pairs (p, hyp) where w^2 + p^2 = hyp^2 and hyp < LIMIT.
    // Generate from primitive Pythagorean triples.
    // Primitive: (m^2-n^2, 2mn, m^2+n^2), m>n>0, gcd(m,n)=1, m-n odd.
    // w can be either leg.

    // We need hyp < LIMIT, so m^2+n^2 < LIMIT for primitive triples,
    // and d*(m^2+n^2) < LIMIT for multiples.

    // Group by w: for each w, list of (p, hyp) pairs.
    // Use a map since w can be up to ~LIMIT.
    unordered_map<int, vector<pair<int,int>>> by_w;

    for (long long m = 2; m * m < LIMIT; m++) {
        for (long long n = 1; n < m; n++) {
            if ((m - n) % 2 == 0) continue;
            if (__gcd(m, n) != 1LL) continue;

            long long w1 = m * m - n * n;
            long long p1 = 2 * m * n;
            long long hyp = m * m + n * n;

            // Multiples: d * (w1, p1, hyp)
            for (long long d = 1; d * hyp < LIMIT; d++) {
                long long w = d * w1, p = d * p1, h = d * hyp;
                by_w[(int)w].push_back({(int)p, (int)h});
            }
            // Also: d * (p1, w1, hyp) - swap legs
            for (long long d = 1; d * hyp < LIMIT; d++) {
                long long w = d * p1, p = d * w1, h = d * hyp;
                by_w[(int)w].push_back({(int)p, (int)h});
            }
        }
    }

    long long answer = 0;

    for (auto& [w, legs] : by_w) {
        int sz = legs.size();
        if (sz < 2) continue;

        // For each pair of triples sharing this w:
        // (p1, hyp1) and (p2, hyp2) where hyp1 < hyp2
        // Check: h = p1*p2/(p1+p2) is integer
        // And hyp1 < hyp2 < LIMIT (already ensured by generation)
        // Count as triplet (hyp1, hyp2, h)

        // Need to avoid double-counting: (x,y) = (hyp1, hyp2) with x < y.
        // A pair of triples (p1,hyp1) and (p2,hyp2) with hyp1 < hyp2 gives one triplet.
        // Same (p1,hyp1) and (p2,hyp2) gives same (x,y) regardless of w.
        // But different w values give different configurations.
        // Actually: the problem counts (x, y, h) triplets. Same x,y might give different h
        // with different w. So each (w, pair) is distinct if h differs.
        // Actually: for given x and y, w is uniquely determined (the crossing geometry
        // determines w from x, y, h). Wait no: for given (x, y), there might be multiple
        // valid w values. But each (x, y, h) triplet is unique because h determines w.
        // h = pq/(p+q). p = sqrt(x^2-w^2), q = sqrt(y^2-w^2). Different w -> different h.
        // So each (w, pair) gives a unique (x, y, h).

        for (int i = 0; i < sz; i++) {
            for (int j = i + 1; j < sz; j++) {
                long long p1 = legs[i].first, hyp1 = legs[i].second;
                long long p2 = legs[j].first, hyp2 = legs[j].second;
                // Ensure x < y (smaller hypotenuse first)
                // hyp1 and hyp2 might be in any order
                if (hyp1 == hyp2) continue; // x < y strictly

                long long g = __gcd(p1, p2);
                long long alpha = p1 / g;
                long long beta = p2 / g;
                // h = g * alpha * beta / (alpha + beta). Integer iff (alpha+beta) | g.
                if (g % (alpha + beta) == 0) {
                    answer++;
                }
            }
        }
    }

    cout << answer << endl;
    return 0;
}

Python project_euler/problem_309/solution.py

"""
Problem 309: Integer Ladders

Two ladders of integer lengths x, y lean against opposite walls of an alley
of integer width w, crossing at integer height h.
x^2 = w^2 + p^2, y^2 = w^2 + q^2, h = pq/(p+q).

Count (x, y, h) triplets with 0 < x < y < 1000000.

For h to be integer: let g=gcd(p,q), p=g*alpha, q=g*beta, gcd(alpha,beta)=1.
Then h = g*alpha*beta/(alpha+beta), integer iff (alpha+beta) | g.

Answer: 210139
"""

from math import gcd
from collections import defaultdict

def solve():
    LIMIT = 1000000

    # For each w, store (other_leg, hypotenuse) pairs
    by_w = defaultdict(list)

    # Generate primitive Pythagorean triples and their multiples
    m = 2
    while m * m < LIMIT:
        for n in range(1, m):
            if (m - n) % 2 == 0:
                continue
            if gcd(m, n) != 1:
                continue

            w1 = m * m - n * n
            p1 = 2 * m * n
            hyp = m * m + n * n

            d = 1
            while d * hyp < LIMIT:
                by_w[d * w1].append((d * p1, d * hyp))
                by_w[d * p1].append((d * w1, d * hyp))
                d += 1

        m += 1

    answer = 0
    for w, legs in by_w.items():
        sz = len(legs)
        if sz < 2:
            continue
        for i in range(sz):
            for j in range(i + 1, sz):
                p1, hyp1 = legs[i]
                p2, hyp2 = legs[j]
                if hyp1 == hyp2:
                    continue  # x < y strictly
                g = gcd(p1, p2)
                alpha = p1 // g
                beta = p2 // g
                if g % (alpha + beta) == 0:
                    answer += 1

    print(answer)