Detailed mathematical approach

Problem Summary

For a target of \(L\) complete loops, we want the smallest number of coins \(N(L)\) whose cumulative turning angle exceeds \(2\pi L\). The checkpoint values used by the implementations are \(N(1)=31\), \(N(2)=154\), and \(N(10)=6947\).

The key observation is that the geometry can be encoded by the harmonic numbers

$H_n=\sum_{k=1}^{n}\frac{1}{k},\qquad r_n=\sqrt{\frac{H_n}{n}},$

so the problem becomes a summation problem for a slowly decreasing sequence of angles rather than a brute-force geometric simulation.

Mathematical Approach

The fast solution separates the angle contributed by the current outer boundary from the much smaller interior angle increments. That makes it possible to keep an exact formulation for small cases and a block-accelerated asymptotic formulation for the large target.

Step 1: Express the Coin Chain as an Angle Sum

For stage \(n\), define two geometric angles by

$\beta_n=\arctan\left(\frac{\sqrt{4-r_n^2}}{r_n}\right),\qquad \gamma_n=\arctan\left(\frac{n\,r_n\sqrt{4-r_n^2}}{n r_n^2+2}\right).$

The turning contributed by the first transition is simply \(\theta_1=\beta_1\). For every later transition, the previously accumulated contact geometry subtracts \(\gamma_{n-1}\), so

$\theta_n=\beta_n-\gamma_{n-1}\qquad (n\ge 2).$

If

$T_m=\sum_{n=1}^{m}\theta_n,$

then \(m\) is the number of completed transitions, and the required number of coins is

$N(L)=m+1.$

Here \(m\) is the first index for which \(T_m>2\pi L\).

Step 2: Simplify the Local Increment

Introduce the smaller angle

$\phi_n=\beta_n-\gamma_n.$

Then the total turn can be rewritten as

$T_m=\beta_m+\sum_{n=1}^{m-1}\phi_n.$

This identity is exactly what the accelerated routine exploits: \(\beta_m\) is a single boundary term, while the long sum consists only of the small increments \(\phi_n\).

Using the tangent subtraction formula and \(r_n^2=H_n/n\), we obtain

$\tan(\phi_n)=\frac{\sqrt{4-r_n^2}}{r_n(2n+1)}=\frac{\sqrt{n/H_n-1/4}}{n+1/2}.$

Therefore

$\phi_n=\arctan\left(\frac{\sqrt{n/H_n-1/4}}{n+1/2}\right),\qquad \beta_n=\arctan\left(\sqrt{\frac{4n}{H_n}-1}\right).$

This is the main closed form behind the implementation.

Step 3: Estimate the Harmonic Numbers for Large \(n\)

Directly updating \(H_n\) term by term is exact, but too slow when the target loop count is large. The code therefore replaces \(H_n\) by its Euler-Maclaurin expansion once \(n\) is big:

$H_n=\log n+\gamma+\frac{1}{2n}-\frac{1}{12n^2}+\frac{1}{120n^4}-\frac{1}{252n^6}+O(n^{-8}),$

where \(\gamma\) is the Euler-Mascheroni constant.

From this we see that

$\phi_n\sim \frac{1}{\sqrt{nH_n}}\sim \frac{1}{\sqrt{n\log n}},$

so the total turn keeps growing, but extremely slowly. That slow divergence is the reason a naive term-by-term scan becomes expensive for the full problem.

Step 4: Replace \(\arctan\) by a Short Odd Polynomial

Let

$x_n=\frac{\sqrt{n/H_n-1/4}}{n+1/2}.$

For large \(n\), this quantity is small, so

$\arctan(x_n)=x_n-\frac{x_n^3}{3}+\frac{x_n^5}{5}+O(x_n^7).$

The bulk summation therefore uses the polynomial

$P(x)=x-\frac{x^3}{3}+\frac{x^5}{5}$

instead of calling the exact inverse tangent at every large index. The implementations also begin the accelerated accumulation with a tiny fixed angular correction, compensating for the small bias introduced by truncating the power series.

Step 5: Sum Large Ranges in Blocks

Define

$\widetilde{H}(t)=\log t+\gamma+\frac{1}{2t}-\frac{1}{12t^2}+\frac{1}{120t^4}-\frac{1}{252t^6},$

and

$f(t)=P\left(\frac{\sqrt{t/\widetilde{H}(t)-1/4}}{t+1/2}\right).$

Over a symmetric block of width \(2k+1\) centered at \(c\), the long sum

$\sum_{j=-k}^{k} f(c+j)$

is approximated by a quadratic model for the interior plus Euler-Maclaurin-style endpoint corrections:

$\sum_{j=-k}^{k} f(c+j)\approx 2k\,f(c)+\frac{k^3}{3}f''(c)+\frac{f(c-k)+f(c+k)}{2}+\frac{f'(c+k)-f'(c-k)}{12}.$

The second derivative and the endpoint derivatives are estimated from the five sampled values \(f(c-2k)\), \(f(c-k)\), \(f(c)\), \(f(c+k)\), and \(f(c+2k)\) via central differences. This lets the program jump over tens of thousands of indices at a time.

Because \(\beta_m<\pi/2\) for every \(m\), the block stage only needs to push the partial sum beyond

$2\pi L-\frac{\pi}{2}.$

After that, a short forward scan with the exact boundary term \(\beta_m\) is enough to finish.

Worked Example: One Full Loop

The first few exact turns are

$\theta_1=\frac{\pi}{3}\approx 1.04719755,\qquad \theta_2\approx 0.59936515,\qquad \theta_3\approx 0.44076494.$

Continuing the exact recurrence gives

$T_{29}\approx 6.24142680<2\pi,\qquad T_{30}\approx 6.33370271>2\pi.$

So 30 transitions are not enough, but 31 coins are enough. Hence

$N(1)=31.$

How the Code Works

The C++, Python, and Java implementations all use the same mathematics. The exact recurrence is retained for small loop counts: it updates \(H_n\), \(r_n\), the carried boundary angle, and the accumulated turn until the threshold \(2\pi L\) is crossed.

For the large target, the implementation first sums a fixed prefix term by term. It then switches to the polynomial model \(P(x)\) together with the harmonic approximation \(\widetilde{H}(n)\), advancing in wide symmetric blocks and estimating the block contribution from five sampled points. Once the reduced target \(2\pi L-\pi/2\) is exceeded, it rolls back one block, rebuilds the local harmonic value, and performs a short final scan while checking the exact boundary term \(\beta_n\).

The C++ version also includes explicit checkpoint assertions for the small cases \(L=1\), \(L=2\), and \(L=10\), confirming that both branches match the same mathematical model.

Complexity Analysis

If the exact branch needs \(m\) transitions, its running time is \(O(m)\) and its memory usage is \(O(1)\).

In the accelerated branch, let \(n_0\) be the fixed prefix length and let \(k\) be the half-width of a block. Then the total work is

$O\!\left(n_0+\frac{m-n_0}{2k+1}+k\right),$

because each wide block is processed in constant time and the tail scan is short. The memory usage remains \(O(1)\). In practice this is the crucial improvement: the program scales with the number of sampled blocks, not with the full number of coins.

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=737
2. Harmonic number: Wikipedia — Harmonic number
3. Euler-Maclaurin formula: Wikipedia — Euler-Maclaurin formula
4. Inverse trigonometric functions: Wikipedia — Inverse trigonometric functions
5. Finite difference: Wikipedia — Finite difference