Detailed mathematical approach

Problem Summary

Scale every circle so that the radius is 1. Then \(n\) congruent circles sit inside a rectangle of width \(2n\) and height \(2\). In the lower-left corner there is a unit square, and the first circle removes a quarter circle from that square. The remaining corner region is the L-section. The concave triangle is the part of that L-section that lies below the diagonal of the full rectangle.

We must find the smallest positive integer \(n\) such that

$\frac{A_C(n)}{A_L} \lt 10^{-3}.$

The geometry becomes manageable because everything reduces to one straight line, one circular arc, and their intersection inside the unit square.

Mathematical Approach

After the radius is normalized to 1, the computation can be written entirely with elementary geometry. The implementations evaluate a closed-form formula for the concave area and then scan upward in \(n\).

Step 1: Normalize the Figure and the Fixed L-Section

Inside the unit square \(0 \le x \le 1\), \(0 \le y \le 1\), the relevant arc comes from the circle centered at \((1,1)\) with radius 1:

$(x-1)^2 + (y-1)^2 = 1.$

We need the lower branch of that circle, so

$y_{\mathrm{arc}}(x) = 1 - \sqrt{1-(x-1)^2} = 1 - \sqrt{2x-x^2}.$

The L-section is the unit square minus the quarter circle. Its area does not depend on \(n\):

$A_L = 1 - \frac{\pi}{4}.$

Step 2: Express the Diagonal as a Line

The diagonal of the \(2n \times 2\) rectangle runs from \((0,0)\) to \((2n,2)\), so its slope is \(1/n\). In the unit square the line is therefore

$y_{\mathrm{line}}(x) = \frac{x}{n}.$

The concave triangle is the part of the L-section below this line. For \(x\) near 0 the line is lower than the arc; after the intersection point, the arc is the lower boundary. That is why the area splits into a line part and an arc part.

Step 3: Solve for the Intersection Point

Let \(x_\ast\) be the intersection abscissa in \((0,1)\). It satisfies

$\frac{x_\ast}{n} = 1 - \sqrt{2x_\ast-x_\ast^2}.$

Move the square root to the right-hand side and square:

$\sqrt{2x_\ast-x_\ast^2} = 1 - \frac{x_\ast}{n},$

$2x_\ast - x_\ast^2 = 1 - \frac{2x_\ast}{n} + \frac{x_\ast^2}{n^2}.$

Multiplying by \(n^2\) gives the quadratic equation

$\left(n^2+1\right)x_\ast^2 - 2n(n+1)x_\ast + n^2 = 0.$

The smaller root is the one that lies inside the unit square:

$x_\ast = \frac{n\left(n+1-\sqrt{2n}\right)}{n^2+1}.$

Step 4: Integrate the Concave Area

The first piece is the area under the line from 0 to \(x_\ast\):

$\int_0^{x_\ast}\frac{x}{n}\,dx = \frac{x_\ast^2}{2n}.$

The second piece is the area under the arc from \(x_\ast\) to 1:

$\int_{x_\ast}^{1}\left(1-\sqrt{2x-x^2}\right)\,dx.$

Set \(u = 1-x\), and write \(\delta = 1-x_\ast\). Since \(2x-x^2 = 1-u^2\), the integral becomes

$\int_0^{\delta}\left(1-\sqrt{1-u^2}\right)\,du.$

Now use the standard antiderivative

$\int \sqrt{1-u^2}\,du = \frac{u\sqrt{1-u^2} + \arcsin(u)}{2}.$

Therefore

$A_C(n) = \frac{x_\ast^2}{2n} + \delta - \frac{\delta\sqrt{1-\delta^2} + \arcsin(\delta)}{2}, \qquad \delta = 1-x_\ast.$

This is exactly the closed form used by the implementation, so no numerical integration is required.

Step 5: Form the Ratio and Search

Once the concave area is known, the target ratio is

$R(n) = \frac{A_C(n)}{A_L} = \frac{A_C(n)}{1-\pi/4}.$

Each evaluation needs only a few square roots, one inverse sine, and basic arithmetic. The implementations therefore test \(n=1,2,3,\dots\) in order and stop at the first value for which \(R(n) \lt 10^{-3}\).

Worked Example: \(n=2\)

For \(n=2\), the intersection simplifies to

$x_\ast = \frac{2\left(3-\sqrt{4}\right)}{5} = \frac{2}{5}, \qquad \delta = \frac{3}{5}.$

The line contribution is

$\frac{x_\ast^2}{2n} = \frac{(2/5)^2}{4} = 0.04.$

The arc contribution is

$\delta - \frac{\delta\sqrt{1-\delta^2} + \arcsin(\delta)}{2} = 0.6 - \frac{0.6 \cdot 0.8 + \arcsin(0.6)}{2} \approx 0.0382494456.$

So

$A_C(2) \approx 0.0782494456,$

while

$A_L = 1 - \frac{\pi}{4} \approx 0.2146018366.$

Hence

$R(2) \approx 0.364626169291728,$

which matches the checkpoint used by the implementations.

How the Code Works

The C++, Python, and Java implementations all follow the same plan. They treat the L-section area \(1-\pi/4\) as a constant, because it does not depend on \(n\). For each trial value of \(n\), they compute the intersection point from the quadratic formula above, convert it into \(\delta = 1-x_\ast\), and evaluate the line piece and the arc piece directly in closed form.

After that, the implementation divides by the fixed L-section area to obtain the ratio and scans upward through positive integers until the threshold \(10^{-3}\) is crossed. One implementation also verifies the checkpoints \(R(1)=0.5\), \(R(2)\approx 0.364626169291728\), and that the \(10\%\) threshold is first met at \(n=15\), which confirms that the geometry and the formula are consistent.

Complexity Analysis

Each candidate \(n\) requires only constant-time floating-point work, so the running time is \(O(n_\star)\), where \(n_\star\) is the first integer satisfying the inequality. The memory usage is \(O(1)\), since only a small fixed set of numeric quantities is stored.

Footnotes and References

1. Problem page: Project Euler 587
2. Circle geometry: Wikipedia — Circle
3. Circular segment: Wikipedia — Circular segment
4. Line-circle intersection: MathWorld — Circle-Line Intersection
5. Inverse trigonometric functions: Wikipedia — Inverse trigonometric functions