Project Euler Problem 309

Project Euler Problem 309

Solution

Answer: 210139

Let the street width be $w$. Suppose the ladders have lengths $x<y$, touching the opposite walls at heights $a$ and $b$, respectively.

By the Pythagorean theorem:

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

so $a,b$ must be integers. The crossing height $h$ satisfies the standard crossing-ladders relation:

$$\frac1h=\frac1a+\frac1b$$

which rearranges to

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

Thus, for integer $h$, we need:

$$a+b \mid ab$$

So the problem becomes:

1. Find all integer right triangles with common leg $w$:

$$x^2=w^2+a^2,\qquad y^2=w^2+b^2$$ 2. For every pair sharing the same $w$, count those with

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

A key observation is that every valid $(w,a,x)$ is a Pythagorean triple. We can generate all such triples efficiently using Euclid’s formula:

$$a=m^2-n^2,\qquad b=2mn,\qquad c=m^2+n^2$$

with $\gcd(m,n)=1$ and opposite parity, then scale by $k$.

For each width $w$, collect all possible ladder configurations $(a,x)$, then test every pair:

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

If $h$ is integral, count the triplet $(x,y,h)$.

---

Python implementation

from math import gcd, isqrt
from collections import defaultdict

LIMIT = 1_000_000

# width -> list of (height, ladder_length)
by_width = defaultdict(list)

# Generate all Pythagorean triples
m_max = isqrt(LIMIT) + 2

for m in range(2, m_max):
    for n in range(1, m):
        # Primitive triple conditions
        if gcd(m, n) != 1 or (m - n) % 2 == 0:
            continue

        a = m * m - n * n
        b = 2 * m * n
        c = m * m + n * n

        k = 1
        while k * c < LIMIT:
            aa = k * a
            bb = k * b
            cc = k * c

            # Either leg can be the street width
            if aa < LIMIT:
                by_width[aa].append((bb, cc))
            if bb < LIMIT:
                by_width[bb].append((aa, cc))

            k += 1

count = 0

# For each common width, test pairs
for w, configs in by_width.items():
    L = len(configs)

    for i in range(L):
        a, x = configs[i]

        for j in range(i + 1, L):
            b, y = configs[j]

            # Need x < y (avoid duplicates)
            if x == y:
                continue

            # h = ab / (a + b) must be integer
            if (a * b) % (a + b) == 0:
                count += 1

print(count)

---

Code walkthrough

• Generate Pythagorean triples

• Euclid’s formula generates every primitive right triangle.

• Multiply by $k$ to obtain all non-primitive ones.

• Store every possibility keyed by common width $w$.

• Pair ladders sharing the same width

• For each width, every stored item is a possible ladder.

• Compare every pair.

• Check integer crossing height

• Use

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

• Count only when divisible.

---

Verification on the small example

For $x,y<200$, the program produces exactly:

$$(70,119,30),; (74,182,21),; (87,105,35),; (100,116,35),; (119,175,40)$$

which matches the problem statement (5 solutions).

The final count for $x,y<1{,}000{,}000$ is:

Answer: 210139