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.
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.
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\).
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.
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.
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.
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.
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.$$
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.
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.
Für ein Ziel von \(L\) vollständigen Umläufen suchen wir die kleinste Anzahl von Münzen \(N(L)\), deren kumulierter Drehwinkel größer als \(2\pi L\) wird. Die in den Implementierungen verwendeten Kontrollwerte sind \(N(1)=31\), \(N(2)=154\) und \(N(10)=6947\).
Der entscheidende Punkt ist, dass sich die Geometrie durch die harmonischen Zahlen
$$H_n=\sum_{k=1}^{n}\frac{1}{k},\qquad r_n=\sqrt{\frac{H_n}{n}}$$
kodieren lässt. Damit wird aus einer geometrischen Konstruktion eine Aufgabe über eine langsam fallende Winkelsumme.
Die schnelle Lösung trennt einen einzelnen Randwinkel von den vielen kleinen Innenbeiträgen. Genau diese Aufspaltung erlaubt eine exakte Methode für kleine Fälle und eine asymptotisch beschleunigte Summation für den großen Zielwert.
Für Stufe \(n\) definieren wir
$$\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).$$
Der erste Übergang liefert \(\theta_1=\beta_1\). Für alle weiteren Übergänge gilt
$$\theta_n=\beta_n-\gamma_{n-1}\qquad (n\ge 2).$$
Setzt man
$$T_m=\sum_{n=1}^{m}\theta_n,$$
dann ist \(m\) die Anzahl abgeschlossener Übergänge, und die gesuchte Münzzahl ist
$$N(L)=m+1.$$
Dabei ist \(m\) der erste Index mit \(T_m>2\pi L\).
Wir führen den kleineren Winkel
$$\phi_n=\beta_n-\gamma_n$$
ein. Dann lässt sich die Gesamtsumme als
$$T_m=\beta_m+\sum_{n=1}^{m-1}\phi_n$$
schreiben. Genau diese Form wird im schnellen Teil ausgenutzt: \(\beta_m\) ist nur ein Randterm, während die lange Summe aus kleinen \(\phi_n\) besteht.
Mit der Tangens-Subtraktionsformel und \(r_n^2=H_n/n\) folgt
$$\tan(\phi_n)=\frac{\sqrt{4-r_n^2}}{r_n(2n+1)}=\frac{\sqrt{n/H_n-1/4}}{n+1/2}.$$
Also gilt
$$\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).$$
Das ist die zentrale geschlossene Formel der Implementierung.
Das exakte Fortschreiben von \(H_n\) ist korrekt, wird für große Ziele aber zu langsam. Deshalb verwendet der Code für große \(n\) die Euler-Maclaurin-Entwicklung
$$H_n=\log n+\gamma+\frac{1}{2n}-\frac{1}{12n^2}+\frac{1}{120n^4}-\frac{1}{252n^6}+O(n^{-8}),$$
wobei \(\gamma\) die Euler-Mascheroni-Konstante ist.
Daraus folgt
$$\phi_n\sim \frac{1}{\sqrt{nH_n}}\sim \frac{1}{\sqrt{n\log n}},$$
also wächst die Gesamtdrehung weiter, aber nur sehr langsam. Gerade diese langsame Divergenz macht eine naive Summation teuer.
Setze
$$x_n=\frac{\sqrt{n/H_n-1/4}}{n+1/2}.$$
Für große \(n\) ist \(x_n\) klein, also
$$\arctan(x_n)=x_n-\frac{x_n^3}{3}+\frac{x_n^5}{5}+O(x_n^7).$$
Der Hauptteil der Summation verwendet deshalb das Polynom
$$P(x)=x-\frac{x^3}{3}+\frac{x^5}{5}$$
anstelle einer exakten Arcustangens-Auswertung bei jedem großen Index. Zusätzlich startet die beschleunigte Routine mit einer winzigen festen Winkelkorrektur, die den durch das abgeschnittene Polynom entstehenden kleinen systematischen Fehler ausgleicht.
Definiere
$$\widetilde{H}(t)=\log t+\gamma+\frac{1}{2t}-\frac{1}{12t^2}+\frac{1}{120t^4}-\frac{1}{252t^6}$$
und
$$f(t)=P\left(\frac{\sqrt{t/\widetilde{H}(t)-1/4}}{t+1/2}\right).$$
Für einen symmetrischen Block der Breite \(2k+1\) um das Zentrum \(c\) wird
$$\sum_{j=-k}^{k} f(c+j)$$
durch ein quadratisches Innenmodell plus Euler-Maclaurin-artige Randkorrekturen angenähert:
$$\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}.$$
Die zweite Ableitung und die Randableitungen werden aus den fünf Werten \(f(c-2k)\), \(f(c-k)\), \(f(c)\), \(f(c+k)\) und \(f(c+2k)\) per zentralen Differenzen geschätzt. Dadurch kann das Programm in sehr großen Sprüngen vorwärtsgehen.
Weil stets \(\beta_m<\pi/2\) gilt, muss die Blockphase nur den reduzierten Zielwert
$$2\pi L-\frac{\pi}{2}$$
überschreiten. Danach genügt ein kurzer Endlauf mit dem exakten Randterm \(\beta_m\).
Die ersten exakten Drehwinkel sind
$$\theta_1=\frac{\pi}{3}\approx 1.04719755,\qquad \theta_2\approx 0.59936515,\qquad \theta_3\approx 0.44076494.$$
Setzt man die exakte Rekurrenz fort, erhält man
$$T_{29}\approx 6.24142680<2\pi,\qquad T_{30}\approx 6.33370271>2\pi.$$
Also reichen 30 Übergänge nicht aus, 31 Münzen aber schon. Damit
$$N(1)=31.$$
Die C++-, Python- und Java-Implementierungen beruhen auf genau denselben Formeln. Für kleine Schleifenzahlen wird die exakte Rekurrenz verwendet: \(H_n\), \(r_n\), der übertragene Randwinkel und die Gesamtdrehung werden Schritt für Schritt aktualisiert, bis \(2\pi L\) überschritten ist.
Für den großen Zielwert summiert die Implementierung zunächst einen festen Präfix termweise. Danach wechselt sie zum Polynom \(P(x)\) und zur Näherung \(\widetilde{H}(n)\), verarbeitet breite symmetrische Blöcke und schätzt deren Beitrag aus fünf Stützstellen. Sobald der reduzierte Zielwert \(2\pi L-\pi/2\) übertroffen ist, wird ein Block zurückgesetzt, der lokale harmonische Wert rekonstruiert und ein kurzer Endlauf mit dem exakten Randterm \(\beta_n\) durchgeführt.
Die C++-Variante enthält zusätzlich explizite Prüfungen für \(L=1\), \(L=2\) und \(L=10\), damit beide Rechenwege am selben mathematischen Modell verankert bleiben.
Benötigt der exakte Zweig \(m\) Übergänge, dann kostet er \(O(m)\) Zeit und \(O(1)\) Speicher.
Im beschleunigten Zweig sei \(n_0\) die feste Präfixlänge und \(k\) die halbe Blockbreite. Dann ist der Gesamtaufwand
$$O\!\left(n_0+\frac{m-n_0}{2k+1}+k\right),$$
weil jeder breite Block in konstanter Zeit behandelt wird und der Endlauf kurz bleibt. Der Speicherbedarf bleibt \(O(1)\). Praktisch ist das die entscheidende Verbesserung: Die Laufzeit hängt von der Anzahl der Blöcke ab, nicht von der vollständigen Münzzahl.
\(L\) tam tur hedefi için, toplam dönme açısı \(2\pi L\) eşiğini geçen en küçük madeni para sayısını \(N(L)\) bulmak istiyoruz. Uygulamaların kullandığı kontrol değerleri \(N(1)=31\), \(N(2)=154\) ve \(N(10)=6947\) şeklindedir.
Çözümdeki temel fikir, geometrinin harmonik sayılarla ifade edilebilmesidir:
$$H_n=\sum_{k=1}^{n}\frac{1}{k},\qquad r_n=\sqrt{\frac{H_n}{n}}.$$
Böylece problem, zor bir geometrik yerleşimi doğrudan taklit etmek yerine, yavaş azalan bir açı dizisini toplamaya dönüşür.
Hızlı yöntem, dış sınırdan gelen tek bir açı terimini, çok sayıdaki küçük iç artışlardan ayırır. Bu ayrım küçük örneklerde tam hesap, büyük hedefte ise blok bazlı asimptotik hızlandırma yapılmasını sağlar.
\(n\). aşama için şu açıları tanımlayalım:
$$\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).$$
İlk geçişte dönme miktarı \(\theta_1=\beta_1\) olur. Daha sonraki her geçiş için ise önceki temas geometrisi \(\gamma_{n-1}\) kadar bir düzeltme getirir:
$$\theta_n=\beta_n-\gamma_{n-1}\qquad (n\ge 2).$$
Eğer
$$T_m=\sum_{n=1}^{m}\theta_n$$
olarak tanımlanırsa, \(m\) tamamlanmış geçiş sayısıdır ve aranan cevap
$$N(L)=m+1.$$
Burada \(m\), \(T_m>2\pi L\) koşulunu sağlayan ilk indextir.
Daha küçük olan şu açıyı tanımlayalım:
$$\phi_n=\beta_n-\gamma_n.$$
O zaman toplam dönme
$$T_m=\beta_m+\sum_{n=1}^{m-1}\phi_n$$
biçimine gelir. Hızlı çözüm tam olarak bu yapıyı kullanır: \(\beta_m\) tek bir sınır terimidir, uzun toplam ise küçük \(\phi_n\) artışlarından oluşur.
Tanjant farkı formülü ve \(r_n^2=H_n/n\) kullanılırsa
$$\tan(\phi_n)=\frac{\sqrt{4-r_n^2}}{r_n(2n+1)}=\frac{\sqrt{n/H_n-1/4}}{n+1/2}$$
elde edilir. Dolayısıyla
$$\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).$$
Uygulamanın temel kapalı formu budur.
\(H_n\)'yi tek tek güncellemek tam sonuç verir, ancak büyük hedefler için yavaştır. Bu nedenle kod, büyük \(n\) için Euler-Maclaurin açılımını kullanır:
$$H_n=\log n+\gamma+\frac{1}{2n}-\frac{1}{12n^2}+\frac{1}{120n^4}-\frac{1}{252n^6}+O(n^{-8}),$$
burada \(\gamma\), Euler-Mascheroni sabitidir.
Buradan
$$\phi_n\sim \frac{1}{\sqrt{nH_n}}\sim \frac{1}{\sqrt{n\log n}}$$
sonucu çıkar. Toplam açı artmaya devam eder, fakat çok yavaş artar. Büyük problemde saf doğrusal taramanın pahalı olmasının sebebi budur.
Şunu tanımlayalım:
$$x_n=\frac{\sqrt{n/H_n-1/4}}{n+1/2}.$$
Büyük \(n\) için \(x_n\) küçük olduğundan
$$\arctan(x_n)=x_n-\frac{x_n^3}{3}+\frac{x_n^5}{5}+O(x_n^7).$$
Bu yüzden uzun toplamda
$$P(x)=x-\frac{x^3}{3}+\frac{x^5}{5}$$
polinomu kullanılır. Ayrıca hızlandırılmış dal, bu kesilmiş seri yaklaşımının biriktirdiği küçük yanlılığı dengelemek için sabit ve çok küçük bir açı düzeltmesiyle başlatılır.
Şimdi
$$\widetilde{H}(t)=\log t+\gamma+\frac{1}{2t}-\frac{1}{12t^2}+\frac{1}{120t^4}-\frac{1}{252t^6}$$
ve
$$f(t)=P\left(\frac{\sqrt{t/\widetilde{H}(t)-1/4}}{t+1/2}\right)$$
tanımlarını yapalım. Merkezi \(c\), yarı genişliği \(k\) olan simetrik bir blok için
$$\sum_{j=-k}^{k} f(c+j)$$
toplamı, iç bölgede kuadratik model ve uçlarda Euler-Maclaurin tipi düzeltmelerle yaklaşık hesaplanır:
$$\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}.$$
\(f''(c)\) ile uç türevleri, \(f(c-2k)\), \(f(c-k)\), \(f(c)\), \(f(c+k)\) ve \(f(c+2k)\) örneklerinden merkezi farklarla kestirilir. Böylece program her seferinde on binlerce indisi atlayabilir.
Her \(m\) için \(\beta_m<\pi/2\) olduğundan, blok aşamasının yalnızca
$$2\pi L-\frac{\pi}{2}$$
seviyesini geçmesi yeterlidir. Sonrasında \(\beta_m\) sınır terimiyle kısa bir son tarama yapılır.
İlk birkaç tam dönme katkısı şöyledir:
$$\theta_1=\frac{\pi}{3}\approx 1.04719755,\qquad \theta_2\approx 0.59936515,\qquad \theta_3\approx 0.44076494.$$
Tam yineleme sürdürüldüğünde
$$T_{29}\approx 6.24142680<2\pi,\qquad T_{30}\approx 6.33370271>2\pi$$
olur. Yani 30 geçiş yetmez, ama 31 para yeter. Sonuç olarak
$$N(1)=31.$$
C++, Python ve Java uygulamaları aynı matematik üzerine kuruludur. Küçük döngü sayıları için tam yineleme kullanılır; burada \(H_n\), \(r_n\), taşınan sınır açısı ve toplam dönme adım adım güncellenir ve \(2\pi L\) eşiği geçildiğinde durulur.
Büyük hedef için önce sabit uzunlukta bir ön ek terim terim toplanır. Sonra \(P(x)\) polinomu ve \(\widetilde{H}(n)\) yaklaşımı kullanılarak geniş simetrik bloklar halinde ilerlenir; her blok katkısı beş örnek noktadan kestirilir. Azaltılmış hedef \(2\pi L-\pi/2\) geçildiğinde bir blok geri alınır, yerel harmonik değer yeniden kurulur ve \(\beta_n\) sınır terimi kontrol edilerek kısa bir ileri tarama yapılır.
C++ sürümü ayrıca \(L=1\), \(L=2\) ve \(L=10\) için açık doğrulamalar içerir; böylece iki hesap yolu aynı matematiksel modele bağlanmış olur.
Tam dalın \(m\) geçişe ihtiyacı varsa zaman maliyeti \(O(m)\), bellek maliyeti \(O(1)\)'dir.
Hızlandırılmış dalda \(n_0\) sabit ön ek uzunluğu ve \(k\) blok yarı genişliği olsun. Toplam iş yükü
$$O\!\left(n_0+\frac{m-n_0}{2k+1}+k\right)$$
olur; çünkü her geniş blok sabit zamanda işlenir ve son tarama kısadır. Bellek kullanımı yine \(O(1)\)'dir. Pratikte asıl kazanç budur: çalışma süresi toplam para sayısıyla değil, örneklenen blok sayısıyla ölçeklenir.
Para un objetivo de \(L\) vueltas completas, buscamos el menor número de monedas \(N(L)\) cuya rotación acumulada supere \(2\pi L\). Los valores de control usados por las implementaciones son \(N(1)=31\), \(N(2)=154\) y \(N(10)=6947\).
La observación decisiva es que la geometría puede codificarse con los números armónicos
$$H_n=\sum_{k=1}^{n}\frac{1}{k},\qquad r_n=\sqrt{\frac{H_n}{n}},$$
de modo que el problema pasa a ser una suma de ángulos que decrecen lentamente, en vez de una simulación geométrica directa y costosa.
La solución rápida separa un único término de borde de una larga suma de incrementos pequeños. Esa separación permite mantener una formulación exacta para los casos pequeños y una aceleración asintótica por bloques para el objetivo grande.
En la etapa \(n\) definimos
$$\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).$$
La primera transición aporta \(\theta_1=\beta_1\). Para las siguientes se resta la geometría ya acumulada:
$$\theta_n=\beta_n-\gamma_{n-1}\qquad (n\ge 2).$$
Si definimos
$$T_m=\sum_{n=1}^{m}\theta_n,$$
entonces \(m\) es el número de transiciones completadas y la respuesta buscada es
$$N(L)=m+1.$$
Aquí \(m\) es el primer índice que cumple \(T_m>2\pi L\).
Introducimos el ángulo pequeño
$$\phi_n=\beta_n-\gamma_n.$$
Con esta notación, el giro total queda
$$T_m=\beta_m+\sum_{n=1}^{m-1}\phi_n.$$
Esta forma es exactamente la que usa la rutina rápida: \(\beta_m\) es un término de borde único, mientras que la suma larga está compuesta por incrementos pequeños \(\phi_n\).
Aplicando la fórmula de la tangente de una diferencia y usando \(r_n^2=H_n/n\), se obtiene
$$\tan(\phi_n)=\frac{\sqrt{4-r_n^2}}{r_n(2n+1)}=\frac{\sqrt{n/H_n-1/4}}{n+1/2}.$$
Por tanto,
$$\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).$$
Esta es la fórmula cerrada central de la implementación.
Actualizar \(H_n\) término a término es exacto, pero demasiado lento para objetivos grandes. Por eso el código usa la expansión de Euler-Maclaurin cuando \(n\) es grande:
$$H_n=\log n+\gamma+\frac{1}{2n}-\frac{1}{12n^2}+\frac{1}{120n^4}-\frac{1}{252n^6}+O(n^{-8}),$$
donde \(\gamma\) es la constante de Euler-Mascheroni.
De aquí se deduce que
$$\phi_n\sim \frac{1}{\sqrt{nH_n}}\sim \frac{1}{\sqrt{n\log n}},$$
de modo que el giro total sigue creciendo, pero muy lentamente. Esa divergencia lenta es la razón principal por la que una suma ingenua resulta cara.
Definimos
$$x_n=\frac{\sqrt{n/H_n-1/4}}{n+1/2}.$$
Como \(x_n\) es pequeño para \(n\) grande, tenemos
$$\arctan(x_n)=x_n-\frac{x_n^3}{3}+\frac{x_n^5}{5}+O(x_n^7).$$
Por eso la suma masiva usa el polinomio
$$P(x)=x-\frac{x^3}{3}+\frac{x^5}{5}$$
en lugar de evaluar la arcotangente exacta en cada índice grande. Además, la acumulación acelerada empieza con una corrección angular fija y muy pequeña que compensa el sesgo total introducido por truncar la serie.
Sea
$$\widetilde{H}(t)=\log t+\gamma+\frac{1}{2t}-\frac{1}{12t^2}+\frac{1}{120t^4}-\frac{1}{252t^6}$$
y
$$f(t)=P\left(\frac{\sqrt{t/\widetilde{H}(t)-1/4}}{t+1/2}\right).$$
En un bloque simétrico de anchura \(2k+1\) centrado en \(c\), la suma
$$\sum_{j=-k}^{k} f(c+j)$$
se aproxima mediante un modelo cuadrático en el interior y correcciones de borde al estilo de Euler-Maclaurin:
$$\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}.$$
La segunda derivada y las derivadas de borde se estiman a partir de los cinco valores \(f(c-2k)\), \(f(c-k)\), \(f(c)\), \(f(c+k)\) y \(f(c+2k)\) usando diferencias centrales. Así el programa puede avanzar por saltos muy grandes.
Como siempre se cumple \(\beta_m<\pi/2\), la etapa por bloques solo necesita superar
$$2\pi L-\frac{\pi}{2}.$$
Después basta un barrido corto usando el término de borde exacto \(\beta_m\).
Los primeros giros exactos son
$$\theta_1=\frac{\pi}{3}\approx 1.04719755,\qquad \theta_2\approx 0.59936515,\qquad \theta_3\approx 0.44076494.$$
Si continuamos la recurrencia exacta, obtenemos
$$T_{29}\approx 6.24142680<2\pi,\qquad T_{30}\approx 6.33370271>2\pi.$$
Por tanto, 30 transiciones no bastan, pero 31 monedas sí. En consecuencia,
$$N(1)=31.$$
Las implementaciones en C++, Python y Java usan la misma matemática. Para números pequeños de vueltas, la rutina exacta actualiza \(H_n\), \(r_n\), el ángulo de borde arrastrado y el giro acumulado hasta sobrepasar \(2\pi L\).
Para el objetivo grande, la implementación suma primero un prefijo fijo término a término. Luego cambia al polinomio \(P(x)\) y a la aproximación \(\widetilde{H}(n)\), avanza en bloques simétricos anchos y estima la contribución de cada bloque con cinco puntos de muestra. Cuando se supera el objetivo reducido \(2\pi L-\pi/2\), se retrocede un bloque, se reconstruye el valor armónico local y se realiza un barrido final corto comprobando el término exacto \(\beta_n\).
La versión en C++ incluye además verificaciones explícitas para \(L=1\), \(L=2\) y \(L=10\), confirmando que ambas rutas computacionales siguen el mismo modelo matemático.
Si la rama exacta necesita \(m\) transiciones, su tiempo de ejecución es \(O(m)\) y su memoria es \(O(1)\).
En la rama acelerada, si \(n_0\) es la longitud fija del prefijo y \(k\) la semianchura del bloque, el trabajo total es
$$O\!\left(n_0+\frac{m-n_0}{2k+1}+k\right),$$
porque cada bloque ancho se procesa en tiempo constante y el barrido final es corto. La memoria sigue siendo \(O(1)\). En la práctica, esta es la mejora decisiva: el tiempo escala con el número de bloques muestreados, no con el número total de monedas.
对给定的 \(L\) 个完整回环，我们要求最小的硬币数 \(N(L)\)，使得累计转角首次超过 \(2\pi L\)。实现中用来校验的方法结果包括 \(N(1)=31\)、\(N(2)=154\) 和 \(N(10)=6947\)。
解法的关键在于：这道题的几何量可以用调和数来编码：
$$H_n=\sum_{k=1}^{n}\frac{1}{k},\qquad r_n=\sqrt{\frac{H_n}{n}}.$$
这样一来，问题就从“直接模拟一串硬币的几何构型”转化为“求一列缓慢衰减的角度之和”，这正是程序能够高效处理大目标的基础。
快速方法把总转角拆成两部分：一个单独的边界角，以及一大串很小的内部增量。小规模时可以直接按精确递推累加；规模大时则对这些小增量做近似和分块求和。
在第 \(n\) 个阶段，定义两个几何角：
$$\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).$$
第一步转动直接就是 \(\theta_1=\beta_1\)。从第二步开始，前面已经形成的接触结构会带来一个扣除项 \(\gamma_{n-1}\)，因此
$$\theta_n=\beta_n-\gamma_{n-1}\qquad (n\ge 2).$$
如果记
$$T_m=\sum_{n=1}^{m}\theta_n,$$
那么 \(m\) 表示已经完成的转动次数，而题目要求的答案就是满足
$$T_m>2\pi L$$
的最小 \(m\) 所对应的硬币数
$$N(L)=m+1.$$
定义更小的局部角
$$\phi_n=\beta_n-\gamma_n.$$
于是总转角可以重写为
$$T_m=\beta_m+\sum_{n=1}^{m-1}\phi_n.$$
这一步非常重要，因为它把“最后一个边界项”与“长长的内部和”分开了。真正需要大规模求和的是 \(\phi_n\)，而不是原始的 \(\theta_n\)。
利用正切差角公式，再结合 \(r_n^2=H_n/n\)，可以把 \(\phi_n\) 的正切完全化简为
$$\tan(\phi_n)=\frac{\sqrt{4-r_n^2}}{r_n(2n+1)}=\frac{\sqrt{n/H_n-1/4}}{n+1/2}.$$
因此
$$\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).$$
这就是三种实现共同依赖的核心闭式表达。
如果每一步都精确更新 \(H_n\)，当然可以得到正确结果，但在目标很大时会太慢。因此程序在大 \(n\) 区间使用 Euler-Maclaurin 展开：
$$H_n=\log n+\gamma+\frac{1}{2n}-\frac{1}{12n^2}+\frac{1}{120n^4}-\frac{1}{252n^6}+O(n^{-8}),$$
其中 \(\gamma\) 是 Euler-Mascheroni 常数。
由此可见
$$\phi_n\sim \frac{1}{\sqrt{nH_n}}\sim \frac{1}{\sqrt{n\log n}}.$$
也就是说，总转角确实会不断增长，但增长得非常慢。正因为这种“发散得很慢”的特性，直接逐项求和在大规模时才会显得低效。
设
$$x_n=\frac{\sqrt{n/H_n-1/4}}{n+1/2}.$$
当 \(n\) 很大时，\(x_n\) 已经很小，因此可用
$$\arctan(x_n)=x_n-\frac{x_n^3}{3}+\frac{x_n^5}{5}+O(x_n^7)$$
代替精确反正切。实现中实际使用的是
$$P(x)=x-\frac{x^3}{3}+\frac{x^5}{5}$$
这个五次奇多项式。由于截断幂级数会积累非常小但稳定的偏差，程序还在快速分支开始时加入了一个极小的固定角度修正，用来把近似和精确模型重新对齐。
定义
$$\widetilde{H}(t)=\log t+\gamma+\frac{1}{2t}-\frac{1}{12t^2}+\frac{1}{120t^4}-\frac{1}{252t^6}$$
以及
$$f(t)=P\left(\frac{\sqrt{t/\widetilde{H}(t)-1/4}}{t+1/2}\right).$$
对于以 \(c\) 为中心、半宽为 \(k\) 的对称区间，程序需要近似
$$\sum_{j=-k}^{k} f(c+j).$$
实现采用“内部二次模型 + 两端修正”的形式：
$$\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}.$$
这里的 \(f''(c)\) 与端点导数并不是解析求出的，而是通过五个采样值 \(f(c-2k)\)、\(f(c-k)\)、\(f(c)\)、\(f(c+k)\)、\(f(c+2k)\) 用中心差分估计得到。这样每处理一个区块，就能一次跨过很多个索引。
又因为所有 \(m\) 都满足 \(\beta_m<\pi/2\)，所以分块阶段只需要把部分和推进到
$$2\pi L-\frac{\pi}{2}$$
之上。到达这里以后，最后的精确边界项 \(\beta_m\) 最多再补一个不到 \(\pi/2\) 的角度，因此只需做很短的一段线性扫描即可确定答案。
前几个精确转角分别是
$$\theta_1=\frac{\pi}{3}\approx 1.04719755,\qquad \theta_2\approx 0.59936515,\qquad \theta_3\approx 0.44076494.$$
继续按精确递推累加，可得
$$T_{29}\approx 6.24142680<2\pi,\qquad T_{30}\approx 6.33370271>2\pi.$$
这说明 30 次转动还不足以完成一整圈，但 31 枚硬币已经足够。因此
$$N(1)=31.$$
C++、Python 和 Java 实现使用的是同一套数学公式。对于较小的回环数，程序直接做精确递推：逐步更新 \(H_n\)、\(r_n\)、被带到下一步的边界角以及累计转角，直到越过 \(2\pi L\)。
对于大目标，程序先逐项累加一个固定长度的前缀，然后切换到 \(P(x)\) 与 \(\widetilde{H}(n)\) 的近似模型，用宽对称区块进行跳跃式前进，并用五个采样点估计每个区块的总贡献。一旦部分和超过 \(2\pi L-\pi/2\)，程序会回退一个区块，恢复该处的局部调和值，再做一小段精确尾扫，同时检查边界项 \(\beta_n\)。
C++ 版本还保留了对 \(L=1\)、\(L=2\) 和 \(L=10\) 的显式校验，用来确认快速路径与小规模精确路径完全一致。
如果精确分支需要处理 \(m\) 次转动，那么时间复杂度是 \(O(m)\)，空间复杂度是 \(O(1)\)。
在加速分支中，设固定前缀长度为 \(n_0\)，块半宽为 \(k\)，则总工作量为
$$O\!\left(n_0+\frac{m-n_0}{2k+1}+k\right).$$
原因是每个大区块只做常数次采样和差分估计，而最后的线性尾扫很短。空间复杂度始终是 \(O(1)\)。从实践上看，真正的提速来源于这里：运行时间取决于采样的区块数，而不是全部硬币数。
Для заданного числа полных витков \(L\) нужно найти минимальное число монет \(N(L)\), при котором накопленный угол поворота впервые превышает \(2\pi L\). В реализации используются контрольные значения \(N(1)=31\), \(N(2)=154\) и \(N(10)=6947\).
Главное наблюдение состоит в том, что геометрию можно переписать через гармонические числа
$$H_n=\sum_{k=1}^{n}\frac{1}{k},\qquad r_n=\sqrt{\frac{H_n}{n}},$$
после чего задача сводится не к прямой геометрической симуляции, а к суммированию медленно убывающей последовательности углов.
Быстрая схема отделяет один граничный угол от длинной суммы малых внутренних приращений. Именно это позволяет сохранить точную формулу для малых случаев и использовать асимптотическое ускорение по блокам для большого целевого значения.
На шаге \(n\) вводятся углы
$$\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).$$
Первый поворот равен \(\theta_1=\beta_1\). Для следующих шагов предыдущая контактная геометрия вычитает \(\gamma_{n-1}\), поэтому
$$\theta_n=\beta_n-\gamma_{n-1}\qquad (n\ge 2).$$
Если положить
$$T_m=\sum_{n=1}^{m}\theta_n,$$
то \(m\) есть число завершенных переходов, а искомое число монет равно
$$N(L)=m+1.$$
Здесь \(m\) — первый индекс, для которого выполняется \(T_m>2\pi L\).
Введем меньший угол
$$\phi_n=\beta_n-\gamma_n.$$
Тогда полная сумма переписывается в виде
$$T_m=\beta_m+\sum_{n=1}^{m-1}\phi_n.$$
Именно эта форма используется в ускоренной части: \(\beta_m\) остается одиночным граничным членом, а длинная сумма состоит из малых слагаемых \(\phi_n\).
Применяя формулу для тангенса разности и подставляя \(r_n^2=H_n/n\), получаем
$$\tan(\phi_n)=\frac{\sqrt{4-r_n^2}}{r_n(2n+1)}=\frac{\sqrt{n/H_n-1/4}}{n+1/2}.$$
Следовательно,
$$\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).$$
Это и есть основная замкнутая формула, лежащая в основе кода.
Точное обновление \(H_n\) по одному члену корректно, но для больших целей слишком медленно. Поэтому для больших \(n\) используется разложение Эйлера-Маклорена:
$$H_n=\log n+\gamma+\frac{1}{2n}-\frac{1}{12n^2}+\frac{1}{120n^4}-\frac{1}{252n^6}+O(n^{-8}),$$
где \(\gamma\) обозначает постоянную Эйлера-Маскерони.
Отсюда следует
$$\phi_n\sim \frac{1}{\sqrt{nH_n}}\sim \frac{1}{\sqrt{n\log n}}.$$
То есть суммарный угол продолжает расти, но растет очень медленно. Именно эта медленная расходимость делает наивное суммирование дорогим.
Положим
$$x_n=\frac{\sqrt{n/H_n-1/4}}{n+1/2}.$$
Для больших \(n\) величина \(x_n\) мала, поэтому
$$\arctan(x_n)=x_n-\frac{x_n^3}{3}+\frac{x_n^5}{5}+O(x_n^7).$$
Основная часть суммирования заменяет точный арктангенс полиномом
$$P(x)=x-\frac{x^3}{3}+\frac{x^5}{5}.$$
Кроме того, ускоренная ветвь начинается с очень маленькой фиксированной угловой поправки, компенсирующей суммарное смещение, возникающее из-за обрезания ряда.
Обозначим
$$\widetilde{H}(t)=\log t+\gamma+\frac{1}{2t}-\frac{1}{12t^2}+\frac{1}{120t^4}-\frac{1}{252t^6}$$
и
$$f(t)=P\left(\frac{\sqrt{t/\widetilde{H}(t)-1/4}}{t+1/2}\right).$$
На симметричном блоке ширины \(2k+1\) с центром \(c\) нужно оценить сумму
$$\sum_{j=-k}^{k} f(c+j).$$
Код аппроксимирует ее квадратичной моделью внутри блока и поправками на концах в духе формулы Эйлера-Маклорена:
$$\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}.$$
Величины \(f''(c)\) и граничные производные оцениваются по пяти значениям \(f(c-2k)\), \(f(c-k)\), \(f(c)\), \(f(c+k)\) и \(f(c+2k)\) с помощью центральных разностей. Это позволяет перескакивать сразу через большие группы индексов.
Поскольку всегда выполняется \(\beta_m<\pi/2\), блочная стадия должна дойти лишь до уровня
$$2\pi L-\frac{\pi}{2}.$$
После этого достаточно короткого финального прохода с точным граничным членом \(\beta_m\).
Первые точные углы равны
$$\theta_1=\frac{\pi}{3}\approx 1.04719755,\qquad \theta_2\approx 0.59936515,\qquad \theta_3\approx 0.44076494.$$
Если продолжить точную рекурсию, получаем
$$T_{29}\approx 6.24142680<2\pi,\qquad T_{30}\approx 6.33370271>2\pi.$$
Значит, 30 переходов недостаточно, а 31 монеты уже достаточно. Следовательно,
$$N(1)=31.$$
Реализации на C++, Python и Java используют одну и ту же математику. Для малых значений числа витков выполняется точная рекурсия: последовательно обновляются \(H_n\), \(r_n\), переносимый граничный угол и накопленный поворот, пока не будет пройден порог \(2\pi L\).
Для большого целевого значения сначала посимвольно суммируется фиксированный префикс. Затем код переключается на полином \(P(x)\) и приближение \(\widetilde{H}(n)\), проходит вперед широкими симметричными блоками и оценивает вклад блока по пяти опорным точкам. Когда превышен уменьшенный порог \(2\pi L-\pi/2\), алгоритм откатывается на один блок, восстанавливает локальное значение гармонической суммы и выполняет короткий финальный проход с проверкой точного граничного члена \(\beta_n\).
Версия на C++ дополнительно содержит явные проверки для \(L=1\), \(L=2\) и \(L=10\), чтобы обе вычислительные ветви оставались согласованы с одной и той же формулой.
Если точная ветвь требует \(m\) переходов, то она работает за \(O(m)\) времени и использует \(O(1)\) памяти.
В ускоренной ветви, если \(n_0\) обозначает длину фиксированного префикса, а \(k\) половину ширины блока, общий объем работы равен
$$O\!\left(n_0+\frac{m-n_0}{2k+1}+k\right),$$
поскольку каждый широкий блок обрабатывается за постоянное время, а финальный линейный хвост короток. Память остается \(O(1)\). На практике это и дает ускорение: время зависит от числа sampled-блоков, а не от полного количества монет.
لعدد مطلوب من اللفات الكاملة \(L\)، نريد أصغر عدد من العملات \(N(L)\) بحيث يتجاوز مجموع زاوية الدوران لأول مرة القيمة \(2\pi L\). وتؤكد التطبيقات قيم التحقق \(N(1)=31\) و\(N(2)=154\) و\(N(10)=6947\).
الفكرة الحاسمة هي أن الهندسة يمكن ترميزها بواسطة الأعداد التوافقية:
$$H_n=\sum_{k=1}^{n}\frac{1}{k},\qquad r_n=\sqrt{\frac{H_n}{n}}.$$
وبذلك تتحول المسألة من محاكاة هندسية مباشرة لسلسلة العملات إلى مسألة جمع زوايا تتناقص ببطء شديد.
الطريقة السريعة تفصل بين حد زاوي واحد على الحافة وبين مجموع طويل من زيادات داخلية صغيرة. هذا الفصل هو ما يسمح بالإبقاء على صياغة دقيقة للحالات الصغيرة، ثم استخدام تسريع تقاربي على هيئة كتل للحالة الكبيرة.
في المرحلة \(n\) نعرّف الزاويتين
$$\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).$$
الدوران الأول يساوي \(\theta_1=\beta_1\). وبعد ذلك تصبح مساهمة كل انتقال
$$\theta_n=\beta_n-\gamma_{n-1}\qquad (n\ge 2).$$
إذا كتبنا
$$T_m=\sum_{n=1}^{m}\theta_n,$$
فإن \(m\) هو عدد الانتقالات المكتملة، ويكون الجواب المطلوب
$$N(L)=m+1.$$
وهنا تكون \(m\) أول قيمة تحقق \(T_m>2\pi L\).
نعرّف الزاوية الأصغر
$$\phi_n=\beta_n-\gamma_n.$$
وعندئذ يصبح مجموع الدوران
$$T_m=\beta_m+\sum_{n=1}^{m-1}\phi_n.$$
هذا هو الشكل الذي تستغله الخوارزمية السريعة: \(\beta_m\) حد حدودي واحد، أما المجموع الطويل فيتكون من زيادات صغيرة \(\phi_n\).
وباستخدام صيغة فرق الظل مع العلاقة \(r_n^2=H_n/n\) نحصل على
$$\tan(\phi_n)=\frac{\sqrt{4-r_n^2}}{r_n(2n+1)}=\frac{\sqrt{n/H_n-1/4}}{n+1/2}.$$
ومن ثم
$$\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).$$
وهذه هي الصيغة المغلقة الأساسية التي تعتمد عليها التطبيقات.
تحديث \(H_n\) حدًا بعد حد دقيق تمامًا، لكنه يصبح بطيئًا عندما يكون الهدف كبيرًا. لذلك يستخدم البرنامج توسع أويلر-ماكلوران عندما تكبر \(n\):
$$H_n=\log n+\gamma+\frac{1}{2n}-\frac{1}{12n^2}+\frac{1}{120n^4}-\frac{1}{252n^6}+O(n^{-8}),$$
حيث \(\gamma\) هو ثابت أويلر-ماسكيروني.
ومن هذا ينتج أن
$$\phi_n\sim \frac{1}{\sqrt{nH_n}}\sim \frac{1}{\sqrt{n\log n}}.$$
أي أن مجموع الزوايا يستمر في الزيادة، لكنه يزداد ببطء شديد. وهذا البطء هو سبب كون الجمع الساذج حدًا بعد حد مكلفًا في المسألة الكاملة.
لنضع
$$x_n=\frac{\sqrt{n/H_n-1/4}}{n+1/2}.$$
عندما تكون \(n\) كبيرة يصبح \(x_n\) صغيرًا، ولذلك
$$\arctan(x_n)=x_n-\frac{x_n^3}{3}+\frac{x_n^5}{5}+O(x_n^7).$$
ولهذا تستعمل الخوارزمية في الجزء الأكبر من الجمع كثير الحدود
$$P(x)=x-\frac{x^3}{3}+\frac{x^5}{5}.$$
كما تبدأ الطريقة المسرّعة بتصحيح زاوي ثابت وصغير جدًا لتعويض الانحياز المتراكم الناتج عن قطع متسلسلة القوى عند الحد الخامس.
نعرّف
$$\widetilde{H}(t)=\log t+\gamma+\frac{1}{2t}-\frac{1}{12t^2}+\frac{1}{120t^4}-\frac{1}{252t^6}$$
و
$$f(t)=P\left(\frac{\sqrt{t/\widetilde{H}(t)-1/4}}{t+1/2}\right).$$
وعلى كتلة متماثلة عرضها \(2k+1\) ومركزها \(c\)، نحتاج إلى تقريب
$$\sum_{j=-k}^{k} f(c+j).$$
ويفعل البرنامج ذلك باستعمال نموذج تربيعي في الداخل مع تصحيحات طرفية من نمط أويلر-ماكلوران:
$$\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}.$$
ويتم تقدير \(f''(c)\) والمشتقات الطرفية من القيم الخمس \(f(c-2k)\) و\(f(c-k)\) و\(f(c)\) و\(f(c+k)\) و\(f(c+2k)\) بواسطة الفروق المركزية. وهكذا يستطيع البرنامج القفز عبر عدد كبير من الفهارس في كل مرة.
ولأن \(\beta_m<\pi/2\) لكل \(m\)، فمرحلة الكتل لا تحتاج إلا إلى دفع المجموع الجزئي فوق
$$2\pi L-\frac{\pi}{2}.$$
بعد ذلك تكفي مسح قصير مع الحد الحدودي الدقيق \(\beta_m\) لإنهاء الحساب.
أول قيم الدوران الدقيقة هي
$$\theta_1=\frac{\pi}{3}\approx 1.04719755,\qquad \theta_2\approx 0.59936515,\qquad \theta_3\approx 0.44076494.$$
وبمتابعة العلاقة الدقيقة نحصل على
$$T_{29}\approx 6.24142680<2\pi,\qquad T_{30}\approx 6.33370271>2\pi.$$
إذن 30 انتقالًا لا تكفي، لكن 31 عملة تكفي. وبالتالي
$$N(1)=31.$$
تعتمد تطبيقات C++ وPython وJava على الرياضيات نفسها. في القيم الصغيرة لعدد اللفات، تستعمل العلاقة الدقيقة مباشرة: يتم تحديث \(H_n\) و\(r_n\) والزاوية الحدية المحمولة والمجموع الكلي حتى يتجاوز العتبة \(2\pi L\).
أما في الهدف الكبير، فتجمع الشيفرة أولًا بادئة ثابتة حدًا بعد حد. ثم تنتقل إلى كثير الحدود \(P(x)\) مع تقريب \(\widetilde{H}(n)\)، وتتحرك إلى الأمام على شكل كتل متماثلة عريضة، وتحسب مساهمة كل كتلة من خمس نقاط عينة. وعندما يتم تجاوز الهدف المخفض \(2\pi L-\pi/2\)، تتراجع الشيفرة كتلة واحدة، وتعيد بناء القيمة التوافقية المحلية، ثم تجري مسحًا نهائيًا قصيرًا مع فحص الحد الدقيق \(\beta_n\).
وتحتوي نسخة C++ كذلك على اختبارات تحقق صريحة للحالات \(L=1\) و\(L=2\) و\(L=10\)، للتأكد من أن المسار الدقيق والمسار المسرّع يطبقان النموذج الرياضي نفسه.
إذا احتاج الفرع الدقيق إلى \(m\) انتقالات، فإن زمنه \(O(m)\) وذاكرته \(O(1)\).
وفي الفرع المسرّع، إذا كانت \(n_0\) طول البادئة الثابتة و\(k\) نصف عرض الكتلة، فإن كلفة العمل الكلية هي
$$O\!\left(n_0+\frac{m-n_0}{2k+1}+k\right),$$
لأن كل كتلة كبيرة تعالج بزمن ثابت، ولأن المسح النهائي قصير. وتبقى الذاكرة \(O(1)\). عمليًا هذه هي نقطة القوة الأساسية: زمن التنفيذ يرتبط بعدد الكتل المعيّنة، لا بعدد العملات كله.