Problem 309: Integer Ladders

Detailed mathematical approach

Problem Summary

Two ladders rest on the opposite walls of a narrow, level street, each with its foot at one wall and its top against the other. Their lengths are \(x\) and \(y\), the street is \(w\) wide, and they cross at height \(h\). The classic crossing-ladders problem gives \(x\), \(y\), \(h\) and asks for \(w\); here all four must be positive integers. The statement offers \(x=70\), \(y=119\), \(h=30\) with \(w=56\), and records that for \(0\lt x\lt y\lt 200\) exactly five triplets \((x,y,h)\) produce an integer \(w\): \((70,119,30)\), \((74,182,21)\), \((87,105,35)\), \((100,116,35)\) and \((119,175,40)\). We must count the triplets \((x,y,h)\) with \(0\lt x\lt y\lt 10^6\) that give an integer \(w\). ^[1]

The whole solution in one sentence: the ladders and the street form two right triangles sharing the street as a leg, so we file every integer right triangle under each of its legs and then, for each width, count the pairs of wall heights \(a,b\) whose \(ab/(a+b)\) is a whole number.

Mathematical Approach

1. The height at which the ladders cross

Let \(a\) be the height at which the ladder of length \(x\) touches its wall, and \(b\) the height for the ladder of length \(y\). Put the street from \(0\) to \(w\), the first ladder from \((0,0)\) to \((w,a)\), the second from \((w,0)\) to \((0,b)\). The ladders are the graphs of \(aX/w\) and \(b(1-X/w)\), equal when \(X(a+b)/w=b\), at \(X=bw/(a+b)\); the height there is

$$h=\frac{ab}{a+b},\qquad\frac1h=\frac1a+\frac1b.$$

So \(h\) is half the harmonic mean of the wall heights and, once \(a\) and \(b\) are known, does not depend on \(w\). ^[2] In the statement's example the wall heights are \(42\) and \(105\), and indeed \(42\cdot105/147=30\).

2. The wall heights are whole numbers too

Each ladder, the street and its wall form a right triangle, so \(a^2=x^2-w^2\) and \(b^2=y^2-w^2\). These are integers, which by itself does not make \(a\) and \(b\) integers, yet the whole search rests on their being so. Write \(A=x^2-w^2\), \(B=y^2-w^2\), so \(a=\sqrt A\) and \(b=\sqrt B\), and suppose \(h\) is a positive integer. Squaring \(1/\sqrt A=1/h-1/\sqrt B\) gives

$$\frac{2}{h\sqrt B}=\frac1{h^2}+\frac1B-\frac1A.$$

The right-hand side is rational and the left-hand side is positive, hence nonzero, so \(\sqrt B\) is rational. A rational number whose square is an integer is an integer: write it as \(r/s\) in lowest terms; from \(r^2=Bs^2\) a prime dividing \(s\) would divide \(r\) too, so \(s=1\). That is the case of the rational root theorem needed here. ^[3] So \(b\) is an integer, and then \(1/\sqrt A=1/h-1/b\) is rational and nonzero, so \(a\) is one as well. A search over all \(w\lt x\lt y\le300\) in exact integer arithmetic finds no solution with an irrational wall height.

3. Two right triangles with a common leg

The problem is therefore to find a positive integer \(w\) and two integer right triangles with legs \((w,a)\) and \((w,b)\), that is

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

such that \(a+b\) divides \(ab\). As \(x\) and \(y\) grow with \(a\) and \(b\), \(x\lt y\) holds exactly when \(a\lt b\), and \(x=y\) is excluded, so \(a\ne b\); both hypotenuses must stay below \(10^6\). Nothing else is needed: a leg is shorter than its hypotenuse, so \(w\lt x\) is automatic.

4. When \(ab/(a+b)\) is a whole number

Let \(g=\gcd(a,b)\) and write \(a=gp\), \(b=gq\) with \(\gcd(p,q)=1\). Then

$$\frac{ab}{a+b}=\frac{g^2pq}{g(p+q)}=\frac{g\,pq}{p+q}.$$

Now \(\gcd(pq,p+q)=1\): a prime dividing \(p+q\) and \(pq\) divides one of \(p,q\), hence the other too, against \(\gcd(p,q)=1\). So the condition is \((p+q)\mid g\), and \(g=(p+q)t\) gives the classical parametrisation of \(1/a+1/b=1/h\), the optic equation: ^[4]

$$\begin{aligned}a&=t\,p(p+q),\\ b&=t\,q(p+q),\\ h&=t\,pq.\end{aligned}$$

The sample pair illustrates it: \(a=42\), \(b=105\) give \(g=21\), \(p=2\), \(q=5\), and \(p+q=7\) divides \(21\) with \(t=3\), so \(h=30\). Rewriting \(ab=h(a+b)\) as \((a-h)(b-h)=h^2\), both factors positive because \(a,b\gt h\), identifies the pairs \(\{a,b\}\) with the factorisations of \(h^2\). Its \(\tau(h^2)\) divisors pair off except the central one, \(h\), so there are \((\tau(h^2)+1)/2\) unordered pairs, \(\tau\) counting divisors. ^[5] For \(h=30\) that is \((27+1)/2=14\); the central divisor gives \(\{60,60\}\), excluded here only because it forces \(x=y\), and of the other \(13\) pairs just \(\{42,105\}\) has a common integer width with both hypotenuses below \(200\). The programs use neither parametrisation, only the test that \(a+b\) divides \(ab\).

5. A worked example: the street of width 56

Exactly seven integer right triangles have a leg of \(56\). Their other legs are \(33\), \(42\), \(90\), \(105\), \(192\), \(390\) and \(783\), with hypotenuses \(65\), \(70\), \(106\), \(119\), \(200\), \(394\) and \(785\). Of the \(21\) pairs of these heights only \(\{42,105\}\) passes the divisibility test, giving \(h=30\) and the ladders \(x=70\), \(y=119\).

Under the example's bound \(x\lt y\lt200\) only the first four survive, since a hypotenuse of \(200\) is already too large. Their six pairs \(\{33,42\}\), \(\{33,90\}\), \(\{33,105\}\), \(\{42,90\}\), \(\{42,105\}\) and \(\{90,105\}\) give \(462/25\), \(990/41\), \(1155/46\), \(315/11\), \(30\) and \(630/13\), so the width \(56\) contributes exactly one triplet below \(200\).

6. The five triplets below 200

Repeating the search over every width reproduces the list of the statement, each triplet from one width and one pair of wall heights:

• \((70,119,30)\) from \(w=56\) with \(\{a,b\}=\{42,105\}\);
• \((74,182,21)\) from \(w=70\) with \(\{24,168\}\);
• \((87,105,35)\) from \(w=63\) with \(\{60,84\}\);
• \((100,116,35)\) from \(w=80\) with \(\{60,84\}\);
• \((119,175,40)\) from \(w=105\) with \(\{56,140\}\).

7. Listing every right triangle

A Pythagorean triple is primitive when its three sides share no divisor above \(1\): \((3,4,5)\) is primitive, \((6,8,10)\) is twice it. Euclid's formula produces every primitive triple exactly once: for \(m\gt n\ge1\) with \(\gcd(m,n)=1\) and \(m-n\) odd,

$$m^2-n^2,\qquad 2mn,\qquad m^2+n^2,$$

and every triple is such a primitive triple times an integer \(k\ge1\). ^[6] Nothing escapes it: in a primitive triple the legs are not both even, nor both odd, as two odd squares leave \(2\) modulo \(4\); with \(\alpha\) the odd leg, \(\beta\) the even one and \(\gamma\) the hypotenuse, \((\gamma+\alpha)/2\) and \((\gamma-\alpha)/2\) are coprime with product \((\beta/2)^2\), so each is a square, \(m^2\) and \(n^2\). As \(m^2+n^2\) is the hypotenuse, the bound \(10^6\) confines \(m\) to \(m\lt1000\). Either leg can be the street, so each triangle is filed under both of its legs, with the other leg and the hypotenuse stored.

Coprime \(m\) and \(n\) that are both odd still give a valid triple, namely twice a primitive one. ^[6] The programs omit the parity test, so every triple with an even scale factor \(k\) appears twice: as \(k\) times a primitive triple and as \(k/2\) times a doubled one. A check over all \(344\,889\) triples with hypotenuse at most \(200\,000\) confirms this multiplicity without exception. Nothing is lost, only time; a set absorbs the duplicates later.

8. How many triangles share a leg

The size of the lists bounds the work. A triangle with legs \(w\), \(a\) and hypotenuse \(x\) satisfies \(w^2=(x-a)(x+a)\), whose factors have equal parity. For odd \(w\) both are odd anyway, so every factorisation \(w^2=uv\) with \(u\lt v\) works: \((\tau(w^2)-1)/2\) triangles. For even \(w\) both factors must be even, and halving them leaves the factorisations of \((w/2)^2\): \((\tau((w/2)^2)-1)/2\) triangles. ^[7] A direct search confirms both formulas for every \(3\le w\lt400\).

These are divisor counts, so they grow very slowly: \(\tau(n)=O(n^{\varepsilon})\) for every \(\varepsilon\gt0\). The widths \(56\), \(70\), \(63\), \(80\) and \(105\) of Section 6 carry \(7\), \(4\), \(7\), \(10\) and \(13\) triangles. Under the hypotenuse bound \(10^6\) the largest number of distinct triangles at one width is \(337\), at \(w=240\,240=2^4\cdot3\cdot5\cdot7\cdot11\cdot13\), a leg of \(850\) triangles in all. With the duplicates of Section 7, the longest list actually stored holds \(605\) entries, at \(w=110\,880\). These stored lengths govern the pair scan and keep it cheap.

9. Why nothing is counted twice or missed

The search enumerates triples \((a,b,w)\) with \(a\lt b\), while the problem counts triplets \((x,y,h)\); the counts agree. Given \(w\), the height \(a\) determines \(x=\sqrt{w^2+a^2}\) and conversely, so \((a,b,w)\) and \((x,y,w)\) say the same thing. And \((x,y,h)\) determines \(w\): let \(w\) grow from \(0\) towards \(x\); both \(\sqrt{x^2-w^2}\) and \(\sqrt{y^2-w^2}\) shrink strictly, so \(1/a+1/b=1/h\) grows strictly and \(h\) shrinks strictly. Each triplet thus belongs to one width and is counted once. Among the \(18\,609\) triplets below \(10^5\), none arises from two widths.

10. Two traps

The width must be part of the key. The height pair \(\{60,84\}\) passes the divisibility test and occurs over two widths: \(w=63\) gives the ladders \(87\) and \(105\), \(w=80\) gives \(100\) and \(116\). Both appear in the list of five, with the same \(h=35\).

Conversely, a pair of ladders is not a triplet. The smallest example is \(x=6902\), \(y=7098\), which crosses at \(h=1209\) over a width of \(6552\) and at \(h=2448\) over a width of \(4998\). Both count, and below \(10^5\) there are \(25\) such pairs, which is why the problem counts \((x,y,h)\) and not \((x,y)\).

How the Code Works

The C++ program ^[8] reads --limit= and --skip-checkpoints in parse_arguments, which rejects a parsed limit below \(3\), although parse_int_after_prefix accumulates the decimal digits in an unchecked int. Triangle generation and the pair search happen in solve. It sets lmt to the limit minus one, the largest permitted hypotenuse, and builds by_width, a vector of lmt+1 lists, where by_width[w] holds the pairs (other leg, hypotenuse) of every right triangle with \(w\) as a leg. The loops over i and j run to root, the integer square root of lmt plus two, keep the coprime pairs, form \(i^2-j^2\), \(2ij\) and \(i^2+j^2\), order the legs, and push the triangle and its multiples into the lists of both legs while the scaled hypotenuse fits. This implements Section 7, omitted parity test and all.

The second phase realises Sections 3 and 4. For each width w the list is sorted, which puts equal heights side by side. For each entry p the inner loop walks the list from the start and breaks at the first entry of the same height, so it visits every occurrence of every smaller height and never a pair of equal heights. A duplicated triangle is thus retested: a height pair with entry multiplicities \(r\) and \(s\) is tested \(rs\) times, at most four by Section 7. The test is \(ab\equiv0\pmod{a+b}\) in 64-bit arithmetic, since a height nears \(10^6\) and the product reaches \(10^{12}\), beyond 32 bits. A success inserts a key of the two heights and the width into uniq, a std::set, where the repeats collapse; the duplicates cost time, not correctness, and by Section 9 the size of the set is the count asked for. Unless --skip-checkpoints is given, main first calls run_checkpoints, which requires solve(200) to return \(5\).

The ports follow the same two phases. Python uses math.gcd, a list of lists and a set of tuples, and its unbounded integers make the overflow question disappear. Java mirrors the C++ structure with its own gcd, a Pair whose compareTo sorts by height and a Triplet with equals and hashCode for a HashSet; it casts the heights to long before multiplying and stores the smaller first, which changes nothing. Both fix the limit at \(10^6\) in the source, so only the C++ program carries the checkpoint against \(5\), enabled by default.

Complexity and Verification

Let \(L\) be the largest allowed hypotenuse. Generation sweeps every pair \(1\le j\lt i\le R\) with \(R=\lfloor\sqrt L\rfloor+2\), that is \(O(L)\) pairs: here \(500\,500\), of which \(304\,911\) are coprime and \(238\,721\) of those also satisfy \(i^2+j^2\le L\). A pair outside that region costs only its gcd. The number of primitive triples with hypotenuse at most \(L\) is asymptotically \(L/(2\pi)\); ^[9] at \(L=999\,999\) the exact count is \(159\,139\) against a prediction of \(159\,155\). Summing over the scale factors adds a harmonic factor, so the triangles are of order \(L\log L\): exactly \(1\,980\,636\), giving \(3\,961\,272\) entries, or \(5\,831\,636\) with the duplicates of Section 7.

The pair scan tests every pair of stored entries of unequal height, so with \(n_w\) the stored length at width \(w\) and \(d_w\) the number of heights stored twice there, the exact test count is

$$T=\sum_w\Bigl(\binom{n_w}{2}-d_w\Bigr).$$

At \(L=999\,999\) this gives \(156\,849\,195\) tests; with the parity filter only \(61\,023\,819\) pairs would remain, so its absence multiplies them by \(2.57\). The C++ and Python loops take \(162\,680\,831\) iterations, counting those that break on an equal height; Java skips lists shorter than two and takes \(162\,533\,516\). Sorting adds \(O(\sum_w n_w\log n_w)\), and each success attempts one insertion, logarithmic in the tree set of C++ and expected constant in the hash sets of the ports. Since \(n_w\) is at most twice a divisor count, \(n_w=O(L^{\varepsilon})\) for every \(\varepsilon\gt0\), bounding the whole run by \(O(L^{1+\varepsilon})\); the measurements show the scan dominating in practice. Storage is \(O(L)\) plus one slot per entry and per accepted key; the peak is about \(99\), \(394\) and \(886\) MiB and the time \(0.44\), \(0.94\) and \(12.8\) s for C++, Java and Python under g++ 16, OpenJDK 17 and CPython 3.11 on one machine.

Beyond the packaged checkpoint, the following was verified for this article. An independent brute force, looping over every width and wall height and testing \(w^2+a^2\) for squareness without Euclid's formula, agrees with the method above at the bounds \(200\), \(500\), \(1000\) and \(2000\): the counts are \(5\), \(29\), \(76\) and \(204\). The fast method then gives \(630\), \(1438\), \(3165\), \(8787\) and \(18\,609\) for \(5000\), \(10^4\), \(2\cdot10^4\), \(5\cdot10^4\) and \(10^5\). All \(18\,609\) solutions below \(10^5\) match Section 4 and none comes from two widths; the divisor formulas of Section 8 match a direct search for every \(3\le w\lt400\). Finally, the three programs print the same value at the full bound.

Footnotes and References

The references below supply the background facts used above. The integrality of the wall heights, the uniqueness of the width behind a triplet, the duplicate structure of the unfiltered sweep and the operation counts are derived or measured here.

1. Project Euler 309 — Integer Ladders. The official statement places two ladders of lengths x and y on the opposite walls of a narrow, level street of width w, crossing at height h, requires all four values to be positive integers, gives the example (70, 119, 30) with w = 56 and the five triplets for 0 < x < y < 200, and asks how many triplets (x, y, h) with 0 < x < y < 1000000 give an integer w.
2. Wikipedia — Crossed ladders problem. The article derives 1/A + 1/B = 1/h from two pairs of similar triangles, calls it the optic equation, notes that h is half the harmonic mean of the wall heights, and gives the integer instance with heights 42 and 105, width 56 and crossing height 30, the example of the statement.
3. Wikipedia — Rational root theorem. A rational root p/q in lowest terms of an integer polynomial has p dividing the constant term and q the leading coefficient; the monic case, called there the integral root theorem, makes a rational root of t² − B an integer, as Section 2 needs for √B.
4. Wikipedia — Optic equation. The article studies 1/a + 1/b = 1/c in positive integers and gives all solutions as a = k·m(m + n), b = k·n(m + n), c = k·m·n with coprime m, n and arbitrary k, the parametrisation derived in Section 4.
5. OEIS A018892 — ways to write 1/n as a sum of two unit fractions. The sequence counts the unordered pairs of unit fractions summing to 1/n and gives (τ(n²) + 1)/2, the count of height pairs for a given crossing height in Section 4.
6. Wikipedia — Pythagorean triple. Euclid's formula m² − n², 2mn, m² + n² gives a primitive triple exactly when m and n are coprime and of opposite parity, and every triple is a primitive one times a positive integer k. Coprime m and n that are both odd yield twice a primitive triple, the duplication analysed in Section 7.
7. OEIS A046079 — number of Pythagorean triangles with leg n. The sequence counts the right triangles, primitive or not, with n as a leg other than the hypotenuse: (τ(n²) − 1)/2 for odd n and (τ((n/2)²) − 1)/2 for even n, the two cases of Section 8.
8. C++ — Euler309.cpp. The linked immutable revision contains parse_arguments with its two options, the width-indexed lists and pair scan of solve, and the run_checkpoints test of solve(200) against 5. It is the implementation record for this article.
9. MathWorld — Pythagorean Triple. The entry reports Lehmer's 1900 result that the number of primitive triples with hypotenuse below N, divided by N, tends to 1/(2π) = 0.1591549…, the estimate used in the complexity section.