Detailed mathematical approach

Problem Summary

The problem reduces the runner-and-swimmer geometry for a regular \(n\)-gon to a critical constant \(\lambda_n\). The implementations first verify two reference cases, the circular limit and the square, and then apply the same formula to the regular hexagon, which is the actual target.

The computation is not a simulation. Instead, it becomes a finite search for the correct angular branch, followed by one closed-form reconstruction of an angle \(\alpha\), and finally the conversion \(\lambda_n=1/\cos\alpha\).

Mathematical Approach

Let

$\theta=\frac{\pi}{n}.$

The derivation used by the implementation expresses the critical ratio through an auxiliary angle \(\alpha\). The formula is piecewise, because the geometry changes when \(2\alpha\) crosses multiples of \(\theta\).

Step 1: Reduce the regular \(n\)-gon by symmetry

A regular \(n\)-gon is invariant under rotation by one side and reflection across the midpoint of a side. Because of that symmetry, the extremal configuration can be described inside a single half-sector of opening \(\theta=\pi/n\).

Instead of tracking a full trajectory, we only need one angle \(\alpha\) that captures the critical geometry. Once \(\alpha\) is known, the desired constant is simply

$\lambda_n=\frac{1}{\cos\alpha}.$

So the whole problem is reduced to determining the correct value of \(\alpha\).

Step 2: Identify the correct branch with an integer \(K\)

The trigonometric derivation is piecewise. On each branch, an integer \(K\) counts how many full angular steps of size \(\theta\) have been crossed before the critical point is reached. The implementation determines \(K\) by scanning integers \(k=0,1,\dots,n\) and evaluating

$f(k)=\sin(k\theta)-(k+n)\tan\theta\,\cos(k\theta).$

The chosen branch index is the largest \(K\) satisfying

$f(K)\lt 0.$

This search is guaranteed to stop because

$f(0)=-n\tan\theta\lt 0,\qquad f(n)=2n\tan\theta\gt 0.$

So a sign change must occur between \(0\) and \(n\), and the last negative value selects the correct branch of the geometric formula.

Step 3: Recover \(\alpha\) after \(K\) is known

For a fixed branch \(K\), the geometry collapses to one cosine equation:

$\cos(2\alpha-K\theta)=\frac{2\sin(K\theta)}{(K+n)\tan\theta}-\cos(K\theta).$

If we denote the right-hand side by \(A_K\), then

$A_K=\frac{2\sin(K\theta)}{(K+n)\tan\theta}-\cos(K\theta),$

and therefore

$\alpha=\frac12\left(K\theta+\arccos(A_K)\right).$

In exact arithmetic, the chosen branch gives \(A_K\in[-1,1]\). Numerically, it is still wise to clip the value into that interval before applying \(\arccos\).

Step 4: Convert the angle into the target constant

After \(\alpha\) has been reconstructed, the answer follows immediately:

$\lambda_n=\frac{1}{\cos\alpha}.$

So the regular-polygon part of the problem has a compact computational form: first a linear search for \(K\), then one inverse cosine, then one reciprocal cosine.

For the actual target \(n=6\), the scan gives \(K=2\). Substituting \(\theta=\pi/6\) yields

$A_2=\frac{2\sin(\pi/3)}{8\tan(\pi/6)}-\cos(\pi/3)=-\frac18,$

so the hexagon constant is

$\lambda_6=\frac{1}{\cos\left(\frac12\left(\frac{\pi}{3}+\arccos\left(-\frac18\right)\right)\right)}.$

Step 5: Check the circular limit

The C++ implementation also validates the limiting circular case. As \(n\to\infty\), we have \(\theta=\pi/n\to0\), and the discrete quantity \(K\theta\) approaches a continuous angle \(\mu\). Using

$n\tan\left(\frac{\pi}{n}\right)\to\pi,$

the branch-boundary equation \(f(K)=0\) becomes

$\sin\mu-(\mu+\pi)\cos\mu=0.$

Dividing by \(\cos\mu\) gives

$\tan\mu=\mu+\pi,$

or equivalently

$\mu+\pi-\tan\mu=0.$

Once \(\mu\) is found, the limit constant is

$\lambda_{\circ}=\frac{1}{\cos\mu}.$

This is exactly the reference value checked numerically before the polygon case is used.

Worked Example: the square reference case

Take \(n=4\). Then \(\theta=\pi/4\) and \(\tan\theta=1\). Evaluate the branch test:

$f(0)=-4\lt 0,\qquad f(1)=\sin\left(\frac{\pi}{4}\right)-5\cos\left(\frac{\pi}{4}\right)=-2\sqrt2\lt 0,$

$f(2)=\sin\left(\frac{\pi}{2}\right)-6\cos\left(\frac{\pi}{2}\right)=1\gt 0.$

So \(K=1\). The cosine argument becomes

$A_1=\frac{2\sin(\pi/4)}{5\tan(\pi/4)}-\cos(\pi/4)=\frac{\sqrt2}{5}-\frac{\sqrt2}{2}=-\frac{3\sqrt2}{10}.$

Hence

$\alpha=\frac12\left(\frac{\pi}{4}+\arccos\left(-\frac{3\sqrt2}{10}\right)\right),$

and therefore

$\lambda_4=\frac{1}{\cos\alpha}\approx 5.78859314.$

This matches the square validation used by the implementation and shows that the branch rule and the closed form are consistent.

How the Code Works

The C++, Python, and Java implementations all follow the same structure. For a regular \(n\)-gon, they compute \(\theta=\pi/n\) and \(\tan\theta\), scan \(k=0\) to \(n\) until the sign test stops being negative, and keep the last valid branch index \(K\).

They then evaluate the cosine argument, clip it into \([-1,1]\) to neutralize round-off drift, recover \(\alpha\) with \(\arccos\), and return \(1/\cos\alpha\). The C++ implementation also performs two sanity checks: it solves the circular limit equation by bisection, and it compares the square result against the known reference value before computing the hexagon case.

No large tables, recursion, or iterative optimization are involved. The whole computation is a direct translation of the trigonometric formulas above.

Complexity Analysis

For a regular \(n\)-gon, the branch scan costs \(O(n)\) time because it checks at most \(n+1\) integers. All remaining work is constant-time trigonometric evaluation, so the polygon calculation uses \(O(1)\) extra memory.

The circular validation uses bisection with a fixed number of iterations, so it is \(O(I)\) with constant \(I\), and still \(O(1)\) memory. For the actual problem instance \(n=6\), the computation is effectively constant time.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=761
2. Regular polygon: Wikipedia — Regular polygon
3. Trigonometric functions: Wikipedia — Trigonometric functions
4. Inverse trigonometric functions: Wikipedia — Inverse trigonometric functions
5. Bisection method: Wikipedia — Bisection method