Problem 309: Integer Ladders

Project Euler Problem 309 Solution

EulerSolve provides an optimized solution for Project Euler Problem 309, Integer Ladders, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary Two ladders of integer lengths $x$ and $y$ lean across a street of integer width $w$, and they cross at integer height $h$. We must count all triplets $(x,y,h)$ with $$0\lt x\lt y\lt 10^6$$ that produce an integer street width $w$. Mathematical Approach 1) Rewrite the geometry using two right triangles Let $a$ and $b$ be the wall-heights reached by the two ladders. Then each ladder forms a right triangle with common horizontal leg $w$: $$x^2=w^2+a^2,\qquad y^2=w^2+b^2.$$ In the classical crossing-ladders geometry, the intersection height is $$h=\frac{ab}{a+b}.$$ So the problem becomes: find two integer right triangles sharing the same width $w$, with integer vertical legs $a,b$, such that $ab/(a+b)$ is also an integer. 2) Generate all integer ladders from Pythagorean triples Every primitive integer right triangle is generated by Euclid's formula $$u>v\ge 1,\qquad \gcd(u,v)=1,\qquad u-v\text{ odd},$$ $$w_0=u^2-v^2,\qquad a_0=2uv,\qquad c_0=u^2+v^2,$$ up to swapping the two legs....

Detailed mathematical approach

Problem Summary

Two ladders of integer lengths $x$ and $y$ lean across a street of integer width $w$, and they cross at integer height $h$. We must count all triplets $(x,y,h)$ with

$$0\lt x\lt y\lt 10^6$$

that produce an integer street width $w$.

Mathematical Approach

1) Rewrite the geometry using two right triangles

Let $a$ and $b$ be the wall-heights reached by the two ladders. Then each ladder forms a right triangle with common horizontal leg $w$:

$$x^2=w^2+a^2,\qquad y^2=w^2+b^2.$$

In the classical crossing-ladders geometry, the intersection height is

$$h=\frac{ab}{a+b}.$$

So the problem becomes: find two integer right triangles sharing the same width $w$, with integer vertical legs $a,b$, such that $ab/(a+b)$ is also an integer.

2) Generate all integer ladders from Pythagorean triples

Every primitive integer right triangle is generated by Euclid's formula

$$u>v\ge 1,\qquad \gcd(u,v)=1,\qquad u-v\text{ odd},$$

$$w_0=u^2-v^2,\qquad a_0=2uv,\qquad c_0=u^2+v^2,$$

up to swapping the two legs. After multiplying by a scale $t$, we get

$$w=t\,w_0,\qquad a=t\,a_0,\qquad x=t\,c_0.$$

The implementation stores, for each width $w$, every possible pair

$$ (a,x) $$

meaning: “there exists a ladder of integer length $x$ crossing a street of width $w$ and reaching height $a$.”

3) Pair two ladders with the same width

For a fixed width $w$, pick two stored entries $(a,x)$ and $(b,y)$ with $a\ne b$. They describe exactly the two ladders of the problem. The crossing height is integer precisely when

$$h=\frac{ab}{a+b}\in\mathbb Z,$$

which is equivalent to the divisibility test

$$ab \bmod (a+b)=0.$$

This is the only remaining condition once the two right triangles are known.

4) Recover the official $(x,y,h)$ triplets

The code stores $(a,b,w)$ internally, but that is equivalent to the official data $(x,y,h)$, because for fixed $w$,

$$x=\sqrt{w^2+a^2},\qquad y=\sqrt{w^2+b^2},\qquad h=\frac{ab}{a+b}.$$

All three are integers by construction plus the divisibility test above.

The sample case

$$x=70,\qquad y=119,\qquad h=30$$

comes from

$$w=56,\qquad a=42,\qquad b=105,$$

since

$$70^2=56^2+42^2,\qquad 119^2=56^2+105^2,\qquad \frac{42\cdot105}{42+105}=30.$$

The source code checkpoint solve(200)=5 matches the five sample triplets on the Project Euler page.

5) Why deduplication is still used

A width can be reached from both leg orders of a primitive triple, and scaled triples can generate the same geometric configuration in different traversal orders. The code sorts the candidates for each width and inserts canonical tuples into a set so that each ladder pair is counted once.

How the Code Works

1) Bucket by width. by_width[w] stores all pairs $(a,x)$ belonging to that street width.

2) Triple generation. The loops over $(i,j)$ generate primitive Pythagorean triples, then scale them while the hypotenuse remains below the limit.

3) Pair scan inside each width. For every width bucket, the code tests every ordered pair of distinct heights and checks whether $(ab)\bmod(a+b)=0$.

4) Canonical set insertion. Valid pairs are inserted into a set to avoid double counting.

5) Final answer. For the Project Euler bound $10^6$, the implementation returns

$$210139.$$

Complexity Analysis

Pythagorean generation is bounded by the usual $u^2+v^2\lt 10^6$ region, and each primitive triple is scaled until the hypotenuse limit is reached. The dominant cost is the pairwise scan inside each width bucket. In practice these buckets stay moderate enough for the method to finish comfortably, and memory is dominated by the width-indexed candidate lists plus the deduplication set.

Problem 309 source code

C++

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <set>
#include <string>
#include <utility>
#include <vector>
#include <cmath>
#include <functional>

namespace {

using i64 = long long;

struct Options {
    int limit = 1000000;
    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, "--limit=", options.limit)) {
            continue;
        }
        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return options.limit >= 3;
}

i64 solve(const int limit) {
    const int lmt = limit - 1;
    std::vector<std::vector<std::pair<int, int>>> by_width(static_cast<std::size_t>(lmt + 1));
    std::set<std::pair<std::pair<int, int>, int>> uniq;

    const int root = static_cast<int>(std::sqrt(static_cast<double>(lmt))) + 2;
    for (int i = 0; i <= root; ++i) {
        for (int j = 1; j < i; ++j) {
            if (std::gcd(i, j) != 1) {
                continue;
            }
            int a = i * i - j * j;
            int b = 2 * i * j;
            int c = i * i + j * j;
            if (a > b) {
                std::swap(a, b);
            }
            for (int scale = 1; scale * c <= lmt; ++scale) {
                by_width[static_cast<std::size_t>(a * scale)].push_back({b * scale, c * scale});
                by_width[static_cast<std::size_t>(b * scale)].push_back({a * scale, c * scale});
            }
        }
    }

    for (int w = 1; w <= lmt; ++w) {
        auto& vec = by_width[static_cast<std::size_t>(w)];
        std::sort(vec.begin(), vec.end());
        for (const auto& p : vec) {
            for (const auto& q : vec) {
                if (p.first == q.first) {
                    break;
                }
                if ((static_cast<i64>(p.first) * static_cast<i64>(q.first)) %
                        static_cast<i64>(p.first + q.first) == 0) {
                    uniq.insert({{p.first, q.first}, w});
                }
            }
        }
    }

    return static_cast<i64>(uniq.size());
}

bool run_checkpoints() {
    if (solve(200) != 5LL) {
        std::cerr << "Checkpoint failed for x<y<200" << '\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.limit) << '\n';
    return 0;
}

Python

import math

def solve():
    limit = 1000000
    lmt = limit - 1

    by_width = [[] for _ in range(lmt + 1)]
    root = int(math.sqrt(lmt)) + 2

    for i in range(root + 1):
        for j in range(1, i):
            if math.gcd(i, j) != 1:
                continue
            a = i*i - j*j
            b = 2*i*j
            c = i*i + j*j
            if a > b:
                a, b = b, a
            scale = 1
            while scale * c <= lmt:
                by_width[a * scale].append((b * scale, c * scale))
                by_width[b * scale].append((a * scale, c * scale))
                scale += 1

    uniq = set()
    for w in range(1, lmt + 1):
        vec = by_width[w]
        if not vec:
            continue
        vec.sort()
        for pi in range(len(vec)):
            for qi in range(len(vec)):
                if vec[pi][0] == vec[qi][0]:
                    break
                h1 = vec[pi][0]
                h2 = vec[qi][0]
                if (h1 * h2) % (h1 + h2) == 0:
                    uniq.add((h1, h2, w))

    return str(len(uniq))

if __name__ == '__main__':
    print(solve())

Java

import java.util.*;

public class Euler309 {
    static int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    static class Pair implements Comparable<Pair> {
        int first, second;

        Pair(int first, int second) {
            this.first = first;
            this.second = second;
        }

        @Override
        public int compareTo(Pair o) {
            if (this.first != o.first)
                return Integer.compare(this.first, o.first);
            return Integer.compare(this.second, o.second);
        }
    }

    static class Triplet {
        int h1, h2, w;

        Triplet(int h1, int h2, int w) {
            this.h1 = h1;
            this.h2 = h2;
            this.w = w;
        }

        @Override
        public boolean equals(Object o) {
            Triplet t = (Triplet) o;
            return h1 == t.h1 && h2 == t.h2 && w == t.w;
        }

        @Override
        public int hashCode() {
            int h = h1;
            h = h * 31 + h2;
            h = h * 31 + w;
            return h;
        }
    }

    public static String solve() {
        int limit = 1000000;
        int lmt = limit - 1;
        List<List<Pair>> byWidth = new ArrayList<>(lmt + 1);
        for (int i = 0; i <= lmt; i++) {
            byWidth.add(new ArrayList<>());
        }

        Set<Triplet> uniq = new HashSet<>();

        int root = (int) Math.sqrt(lmt) + 2;
        for (int i = 1; i <= root; ++i) {
            for (int j = 1; j < i; ++j) {
                if (gcd(i, j) != 1)
                    continue;
                int a = i * i - j * j;
                int b = 2 * i * j;
                int c = i * i + j * j;
                if (a > b) {
                    int temp = a;
                    a = b;
                    b = temp;
                }
                for (int scale = 1; scale * c <= lmt; ++scale) {
                    byWidth.get(a * scale).add(new Pair(b * scale, c * scale));
                    byWidth.get(b * scale).add(new Pair(a * scale, c * scale));
                }
            }
        }

        for (int w = 1; w <= lmt; ++w) {
            List<Pair> vec = byWidth.get(w);
            if (vec.size() < 2)
                continue;
            Collections.sort(vec);
            for (int pIdx = 0; pIdx < vec.size(); ++pIdx) {
                long pf = vec.get(pIdx).first;
                for (int qIdx = 0; qIdx < vec.size(); ++qIdx) {
                    long qf = vec.get(qIdx).first;
                    if (pf == qf)
                        break;
                    if ((pf * qf) % (pf + qf) == 0) {
                        uniq.add(new Triplet((int) qf, (int) pf, w));
                    }
                }
            }
        }

        return String.valueOf(uniq.size());
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}