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.

Further Reading

1. Problem page: https://projecteuler.net/problem=309
2. Pythagorean triples: https://en.wikipedia.org/wiki/Pythagorean_triple
3. Crossing ladders formula: https://en.wikipedia.org/wiki/Crossing_ladders