Detailed mathematical approach

Problem Summary

For a positive radius \(R\), let \(F(R)\) denote the largest possible inradius of a primitive integer right triangle that fits strictly inside a circle of radius \(R\). If the legs are \(a\) and \(b\), the hypotenuse is \(c\), and the inradius is \(r\), the challenge is to evaluate \(F(10^{18})\).

The geometric condition is much simpler than it first appears. A right triangle has circumradius \(c/2\), so fitting strictly inside the circle is equivalent to requiring \(c<2R\). The solution therefore becomes an optimization over primitive Pythagorean triples, and the implementations succeed by combining an exact formula for \(r\), a monotonicity argument for fixed parameters, and an exact continuous upper bound that collapses the search interval.

Mathematical Approach

From the circle constraint to Euclid's parameters

Every primitive Pythagorean triple can be written uniquely as

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

with integers \(m>n>0\), \(\gcd(m,n)=1\), and \(m\not\equiv n\pmod 2\). Since the triangle is right-angled, its smallest enclosing circle has radius \(c/2\), so the condition \(c<2R\) becomes

$m^2+n^2<2R.$

Because the inequality is strict, it is convenient to set

$T=2R-1,$

so that admissible pairs are exactly those with

$m^2+n^2\le T.$

For a right triangle the inradius is

$r=\frac{a+b-c}{2},$

and substituting Euclid's formulas gives the remarkably simple objective

$r=\frac{(m^2-n^2)+2mn-(m^2+n^2)}{2}=n(m-n).$

So the entire problem becomes

$F(R)=\max\left\{n(m-n):m>n>0,\ \gcd(m,n)=1,\ m\not\equiv n\pmod 2,\ m^2+n^2\le T\right\}.$

Why each \(n\) has a single best partner

Fix \(n\). Then the score \(n(m-n)\) increases strictly with \(m\), so only the largest admissible \(m\) can be optimal for that \(n\). Ignoring parity and coprimality for a moment, the geometric ceiling is

$m_{\max}(n)=\left\lfloor \sqrt{T-n^2}\right\rfloor.$

If \(m_{\max}(n)\le n\), then no triangle exists for that \(n\). Otherwise the primitive-triple conditions are enforced in the only direction that matters: start from \(m_{\max}(n)\), decrease once if \(m\) has the same parity as \(n\), and then keep decreasing by \(2\) until \(\gcd(m,n)=1\). The first pair that survives is already the best one for that \(n\), because every later candidate has a smaller \(m\) and therefore a smaller inradius.

This also yields the natural outer range for the search. Since every feasible pair has \(m>n\), we must have

$2n^2<m^2+n^2\le T,$

hence

$1\le n\le \left\lfloor \sqrt{\frac{T}{2}}\right\rfloor=\left\lfloor \sqrt{\frac{2R-1}{2}}\right\rfloor.$

The continuous envelope that makes pruning exact

Now relax the arithmetic conditions and allow \(m\) to move on the real boundary \(m=\sqrt{T-n^2}\). Then every integer candidate with the same \(n\) satisfies

$r\le U(n):=n\left(\sqrt{T-n^2}-n\right).$

This function is a true upper bound, not a heuristic estimate. Differentiating \(U(n)\) shows that its unique peak occurs when the boundary value of \(m\) and the chosen \(n\) satisfy

$m=(1+\sqrt 2)\,n.$

Equivalently, the maximizing real \(n\) satisfies

$n_0^2=\frac{T}{4+2\sqrt 2}=\frac{2R-1}{4+2\sqrt 2}.$

So the best triangle must lie near one continuous optimum rather than somewhere arbitrary in the whole interval. Once a current record is known, every \(n\) with \(U(n)\) no larger than that record can be discarded immediately. Because \(U(n)\) rises to a single peak and then falls, the surviving region is one interval around \(n_0\), which can be found accurately by bisection on the left and right sides.

Worked Example: \(R=100\)

Here \(T=199\), so admissibility means

$m^2+n^2\le 199.$

The continuous peak is near

$n_0\approx \sqrt{\frac{199}{4+2\sqrt 2}}\approx 5.40,$

which already tells us that the optimum should occur close to \(n=5\). For \(n=4\),

$m_{\max}(4)=\left\lfloor \sqrt{199-16}\right\rfloor=13.$

The pair \((13,4)\) already has opposite parity and \(\gcd(13,4)=1\), so it produces

$a=13^2-4^2=153,\qquad b=2\cdot 13\cdot 4=104,\qquad c=13^2+4^2=185,$

and therefore

$r=4(13-4)=36.$

Since \(c/2=92.5<100\), the triangle really does fit inside the circle. Nearby candidates are slightly worse: \(n=5\) leads to \(m=12\) and \(r=35\), while \(n=6\) leads to \(m=11\) and \(r=30\). Thus \(F(100)=36\).

How the Code Works

Shared search strategy

The C++, Python, and Java implementations all follow the same logic. They compute exact integer square roots so that the strict boundary \(m^2+n^2<2R\) is handled as \(m^2+n^2\le 2R-1\) without any floating-point off-by-one errors. They then estimate the location of the continuous peak with \(n_0\approx\sqrt{(2R-1)/(4+2\sqrt 2)}\), scan a wide window around that point to obtain a strong initial record, and evaluate each tested \(n\) by starting from \(\lfloor\sqrt{2R-1-n^2}\rfloor\), fixing parity if necessary, and descending by \(2\) until a coprime partner is found.

Exact pruning and final sweep

After the initial window, the implementations use the upper envelope \(U(n)=n(\sqrt{2R-1-n^2}-n)\) to determine which \(n\)-values can still beat the current best answer. Because \(U\) is unimodal, bisection on each side of the peak isolates the real interval where improvement is still possible. That interval is then converted back to integers and widened slightly to stay safe against rounding.

Inside the final sweep, the code applies the sharper integer bound

$n\left(\left\lfloor\sqrt{2R-1-n^2}\right\rfloor-n\right)$

before spending time on gcd tests. If even this value cannot improve the current record, that \(n\) is skipped immediately. The pruning is therefore exact: every discarded case has been eliminated by a proved upper bound.

Complexity Analysis

The natural search variable is \(n\), and its full admissible range has size \(O(\sqrt R)\). For each tested \(n\), the implementation performs one integer square root, possibly one parity correction, and then a downward walk through values of the correct parity until it reaches a coprime partner. So the basic structure is an \(O(\sqrt R)\)-sized search with very small per-candidate work in practice.

The continuous bound \(U(n)\) makes the real running time much smaller than a full scan, because once a good record is found only a narrow band around the peak can remain relevant. Memory usage is \(O(1)\), since the algorithm stores only a small number of integer and floating-point variables.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=914
2. Pythagorean triple: Wikipedia - Pythagorean triple
3. Incircle and excircles of a triangle: Wikipedia - Incircle and excircles of a triangle
4. Thales's theorem: Wikipedia - Thales's theorem
5. Greatest common divisor: Wikipedia - Greatest common divisor
6. Integer square root: Wikipedia - Integer square root