Project Euler Problem 587 Statement
A square is drawn around a circle as shown in the diagram below on the left.
We shall call the blue shaded region the L-section.
A line is drawn from the bottom left of the square to the top right as shown in the diagram on the right.
We shall call the orange shaded region a concave triangle.
It should be clear that the concave triangle occupies exactly half of the L-section.
Two circles are placed next to each other horizontally, a rectangle is drawn around both circles, and a line is drawn from the bottom left to the top right as shown in the diagram below.
This time the concave triangle occupies approximately 36.46% of the L-section.
If $n$ circles are placed next to each other horizontally, a rectangle is drawn around the n circles, and a line is drawn from the bottom left to the top right, then it can be shown that the least value of n for which the concave triangle occupies less than 10% of the L-section is $n = 15$.
What is the least value of $n$ for which the concave triangle occupies less than 0.1% of the L-section?
Solution
Project Euler Problem 587 overview:
Project Euler problem 587 involves a geometric configuration where a circle is inscribed in a square and the area outside the circle (the L-section) is split by a diagonal into two regions, one forming a concave triangle. When this setup is extended to $n$ side-by-side circles enclosed in a rectangle, the area of the concave triangle relative to the L-section decreases as $n$ increases. While the concave triangle occupies about 36.46% of the L-section for two circles and drops below 10% for $n=15$, the problem asks for the smallest $n$ such that this ratio is less than 0.1%.
Solution Summary
The solution computes the area of the concave triangle by first finding the intersection point between the circle $(x−1)^2+(y−1)^2=1$ and the diagonal $y=x/n$. This point is used to divide the area into simple shapes: a triangle between the intersection, the circle’s center, and a vertical point, a circular sector (pie slice), and another triangle at the origin. The concave triangle’s area is then given by adding the two triangle areas and subtracting the circular sector’s area (and doubling for symmetry). Dividing this area by the L-section area, and searching for the smallest $n$ such that the ratio falls below 0.1%.
Solution Detail
1. Geometry Setup
1.1 Single Circle Case
Consider a circle of radius 1 centered at $(1, 1)$ inside a square with corners at $(0, 0)$, $(2, 0)$, $(2, 2)$, and $(0, 2)$.
- The square’s area is $2 \times 2 = 4.$
- The circle’s area is $\pi.$
- The area outside the circle but inside the square is $4 - \pi.$
The bottom-left L-section is defined as one-quarter of the area outside the circle. Thus, for a single circle: $$\text{L-section area} = \frac{4 - \pi}{4}.$$
A diagonal is drawn from the bottom-left corner $(0, 0)$ to the top-right corner $(2, 2)$, i.e., along the line $y = x.$ The concave triangle is the region of the L-section below this line (but outside the circle). By symmetry, its area is exactly half of the L-section.
Python Source Code
from math import sqrt, pi, asin
def f(k):
x = (1 + k - sqrt(2*k)) / (1 + k**2)
return (k + (1-k) * (1-x) - asin(1-x)) / (2*(1 - pi/4))
n = 1
while f(1 / n) > 0.001:
n += 1
print(n)