For each prime \(p \le n\), the walk uses the irrational step length
$$\alpha_p=\sqrt{\frac{1}{p}}.$$
Starting from \(0\) on the unit circle, the \(k\)-th landing point is the fractional part
$$x_k=\{k\alpha_p\}.$$
A gap of width \(g\) is placed at \([d,d+g)\), where the start point \(d\) ranges over the admissible domain \(0 \le d \le 1-g\). The first hit time is
$$T_{\alpha_p}(d)=\min\{k\ge 1:x_k\in[d,d+g)\}.$$
The contribution of that prime is weighted by the step length itself:
$$S(\alpha_p,g,d)=\alpha_p\,T_{\alpha_p}(d).$$
The full problem asks for the exact maximum
$$M(n,g)=\max_{0\le d\le 1-g}\sum_{\substack{p\le n\\ p\text{ prime}}} S(\alpha_p,g,d).$$
A naive scan over many values of \(d\) is unreliable, because the optimum can sit on very small intervals. The implemented solution therefore represents the function of \(d\) exactly as a finite piecewise-constant object and maximizes that representation directly.
The key observation is that for a fixed prime, the first-hit time depends on \(d\) only through a set of intervals. Once those intervals are known, the sum over all primes can be optimized with a standard sweep over change points.
Fix one prime \(p\) and abbreviate \(\alpha=\alpha_p=\sqrt{1/p}\). Because \(p\) is not a perfect square, \(\alpha\) is irrational. The sequence
$$x_k=\{k\alpha\},\qquad k=1,2,3,\dots,$$
is therefore an irrational rotation on the unit circle. For the problem we do not need a symbolic formula for every \(x_k\); we only need to know where each landing point places the left end of a gap that would be hit at that step.
The event "\(k\)-th jump lands inside the gap" means
$$x_k\in[d,d+g).$$
Solving this inequality for the gap start \(d\) gives
$$d\le x_k\lt d+g\iff d\in(x_k-g,x_k].$$
So every landing point paints an interval of admissible starts. After intersecting with the valid domain, the interval contributed by jump \(k\) is
$$I_k=(x_k-g,x_k]\cap[0,1-g].$$
Endpoint conventions affect only measure-zero boundary points, so they do not change the maximum value of the final function.
The first-hit time is not obtained by taking the union of all intervals blindly. Instead, we keep the still-uncovered portion of \([0,1-g]\). When jump \(k\) produces the interval \(I_k\), only the overlap with the uncovered set receives the label \(k\). Any point already painted earlier keeps its earlier label, because we are recording the first hit time.
This produces a disjoint collection of segments on which
$$T_\alpha(d)=k$$
is constant. Because \(\alpha\) is irrational, the orbit is dense modulo \(1\); with fixed positive gap width \(g\), every admissible start is eventually hit. Once the whole domain has been painted, later jumps cannot change \(T_\alpha\).
After the first-hit segmentation is known, the prime contribution is immediate:
$$S(\alpha,g,d)=\alpha\,T_\alpha(d).$$
Therefore \(S(\alpha,g,d)\) is also piecewise constant on the same segments. For a single prime, the only locations where its value can change are the starts of those segments. That is exactly the information we need to preserve for the global maximum.
Let
$$F(d)=\sum_{\substack{p\le n\\ p\text{ prime}}} S(\alpha_p,g,d).$$
Each summand is piecewise constant, so \(F(d)\) is piecewise constant as well. Its value can change only when at least one prime starts a new segment. If we list every such segment start as an event and sort the events from left to right, then between two consecutive events the sum stays unchanged.
Suppose a single prime contribution changes at some event from \(v_{\text{old}}\) to \(v_{\text{new}}\). Then the running total updates by
$$F_{\text{new}}=F_{\text{old}}-v_{\text{old}}+v_{\text{new}}.$$
Taking the maximum over all plateaus visited by the sweep yields the exact value of \(M(n,g)\). No sampling of \(d\) is needed.
Here the admissible domain is \([0,0.8]\). The first few landing points are
$$x_1\approx 0.7071,\quad x_2\approx 0.4142,\quad x_3\approx 0.1213,\quad x_4\approx 0.8284,\quad x_5\approx 0.5355,\quad x_6\approx 0.2426.$$
They generate the raw intervals
$$I_1\approx(0.5071,0.7071],\quad I_2\approx(0.2142,0.4142],\quad I_3\approx(0,0.1213],$$
$$I_4\approx(0.6284,0.8],\quad I_5\approx(0.3355,0.5355],\quad I_6\approx(0.0426,0.2426].$$
After removing pieces that were already covered earlier, the first-hit function becomes
$$T_\alpha(d)=1\text{ on }(0.5071,0.7071],\qquad T_\alpha(d)=2\text{ on }(0.2142,0.4142],$$
$$T_\alpha(d)=3\text{ on }(0,0.1213],\qquad T_\alpha(d)=4\text{ on }(0.7071,0.8],$$
$$T_\alpha(d)=5\text{ on }(0.4142,0.5071],\qquad T_\alpha(d)=6\text{ on }(0.1213,0.2142].$$
This toy example shows the exact logic of the algorithm: every new jump only claims the starts that were still uncovered, and the resulting segment starts are the events used in the final sweep.
The C++, Python, and Java implementations follow the same mathematical plan. They first enumerate all primes up to \(n\), convert each prime into the irrational step length \(\sqrt{1/p}\), and then build the first-hit segmentation on \([0,1-g]\) for that prime alone. The uncovered part of the domain is stored in an ordered interval structure, so each new jump can subtract its overlap and record exactly which pieces receive the current hit time.
After one prime has been processed, the implementation knows a sequence of disjoint segments and the constant weighted value \(\alpha_p T_{\alpha_p}(d)\) on each of them. The value on the leftmost segment initializes the running total at the start of the domain, while every later segment start becomes an event carrying a replacement value for that prime. All events from all primes are then sorted, scanned once from left to right, and used to update the current total and the best value seen so far.
One implementation also checks the published checkpoints
$$M(3,0.06)=29.5425,\qquad M(10,0.01)=266.9010$$
before evaluating the final case. The Python version delegates the heavy numerical work to the same compiled solver, so the numerical behavior matches the C++ implementation.
Let \(P=\pi(n)\) be the number of primes up to \(n\). For a given prime \(p\), let \(K_p\) be the number of jump positions examined until the whole domain is covered, and let \(J_p\) be the number of stored first-hit segments. Using an ordered interval structure, the per-prime construction is roughly \(O((K_p+J_p)\log J_p)\) in practice. If
$$E=\sum_{p\le n} J_p$$
is the total number of segment starts across all primes, then the global event sort costs \(O(E\log E)\), the sweep itself costs \(O(E)\), and the memory usage is \(O(E+P)\). The method is efficient because it works with exact change points instead of a dense grid of candidate \(d\)-values.
Für jede Primzahl \(p \le n\) wird die irrationale Sprunglänge
$$\alpha_p=\sqrt{\frac{1}{p}}$$
verwendet. Auf dem Einheitskreis liegt der \(k\)-te Punkt der Bahn bei
$$x_k=\{k\alpha_p\}.$$
Eine Lücke der Breite \(g\) beginnt bei \([d,d+g)\), wobei \(d\) im zulässigen Bereich \(0 \le d \le 1-g\) liegt. Die erste Treffzeit ist
$$T_{\alpha_p}(d)=\min\{k\ge 1:x_k\in[d,d+g)\}.$$
Der Beitrag dieser Primzahl wird mit der Sprunglänge gewichtet:
$$S(\alpha_p,g,d)=\alpha_p\,T_{\alpha_p}(d).$$
Gesucht ist also
$$M(n,g)=\max_{0\le d\le 1-g}\sum_{\substack{p\le n\\ p\text{ prim}}} S(\alpha_p,g,d).$$
Eine grobe Abtastung vieler \(d\)-Werte ist ungeeignet, weil das Maximum auf sehr kleinen Teilintervallen liegen kann. Deshalb konstruiert die Lösung die Funktion in \(d\) exakt als endliche stückweise konstante Funktion.
Für eine feste Primzahl hängt die erste Treffzeit nur davon ab, welche Intervalle der Startpunkt \(d\) durch die Bahn trifft. Sind diese Intervalle bekannt, lässt sich die Summe über alle Primzahlen mit einem Sweep über Änderungsstellen exakt maximieren.
Fixiere eine Primzahl \(p\) und schreibe \(\alpha=\alpha_p=\sqrt{1/p}\). Da \(p\) kein Quadrat ist, ist \(\alpha\) irrational. Damit ist
$$x_k=\{k\alpha\},\qquad k=1,2,3,\dots,$$
eine irrationale Rotation modulo \(1\). Für das Problem ist entscheidend, welche Startpunkte \(d\) von einem bestimmten Landepunkt \(x_k\) getroffen werden.
Der \(k\)-te Sprung trifft die Lücke genau dann, wenn
$$x_k\in[d,d+g)$$
gilt. Nach \(d\) aufgelöst ist das äquivalent zu
$$d\le x_k\lt d+g\iff d\in(x_k-g,x_k].$$
Jeder Landepunkt erzeugt also ein Intervall möglicher Lückenstarts. Im zulässigen Bereich bleibt
$$I_k=(x_k-g,x_k]\cap[0,1-g].$$
Unterschiede an Randpunkten haben Maß \(0\) und ändern den Endwert daher nicht.
Für die erste Treffzeit genügt es nicht, alle Intervalle zu vereinigen. Man verwaltet stattdessen den noch unbedeckten Teil von \([0,1-g]\). Wenn der \(k\)-te Sprung das Intervall \(I_k\) liefert, erhält nur der Schnitt von \(I_k\) mit der noch unbedeckten Menge den Wert \(k\). Bereits früher erreichte Punkte behalten ihren kleineren Zeitpunkt.
So entsteht eine disjunkte Zerlegung, auf der
$$T_\alpha(d)=k$$
konstant ist. Weil \(\alpha\) irrational ist, ist die Bahn dicht modulo \(1\); bei festem positivem \(g\) wird daher jeder zulässige Startpunkt irgendwann getroffen. Sobald der ganze Bereich bemalt ist, können spätere Sprünge nichts mehr ändern.
Ist die Segmentierung der ersten Treffzeit bekannt, folgt sofort
$$S(\alpha,g,d)=\alpha\,T_\alpha(d).$$
Damit ist auch der gewichtete Beitrag einer einzelnen Primzahl stückweise konstant. Wertänderungen treten nur an den Anfängen der erzeugten Segmente auf.
Setze
$$F(d)=\sum_{\substack{p\le n\\ p\text{ prim}}} S(\alpha_p,g,d).$$
Da jeder Summand stückweise konstant ist, gilt das auch für \(F(d)\). Die Summe kann sich nur an Stellen ändern, an denen mindestens eine Primzahl ein neues Segment beginnt. Man sammelt daher alle Segmentanfänge als Ereignisse, sortiert sie von links nach rechts und hält die aktuelle Summe während des Sweeps aktuell.
Wechselt bei einem Ereignis ein einzelner Primzahlbeitrag von \(v_{\text{alt}}\) zu \(v_{\text{neu}}\), dann gilt
$$F_{\text{neu}}=F_{\text{alt}}-v_{\text{alt}}+v_{\text{neu}}.$$
Das Maximum über alle dazwischenliegenden Plateaus ist genau \(M(n,g)\).
Hier ist der zulässige Bereich \([0,0.8]\). Die ersten Landepunkte lauten
$$x_1\approx 0.7071,\quad x_2\approx 0.4142,\quad x_3\approx 0.1213,\quad x_4\approx 0.8284,\quad x_5\approx 0.5355,\quad x_6\approx 0.2426.$$
Daraus entstehen die Rohintervalle
$$I_1\approx(0.5071,0.7071],\quad I_2\approx(0.2142,0.4142],\quad I_3\approx(0,0.1213],$$
$$I_4\approx(0.6284,0.8],\quad I_5\approx(0.3355,0.5355],\quad I_6\approx(0.0426,0.2426].$$
Nach Entfernen bereits früher abgedeckter Teile erhält man
$$T_\alpha(d)=1\text{ auf }(0.5071,0.7071],\qquad T_\alpha(d)=2\text{ auf }(0.2142,0.4142],$$
$$T_\alpha(d)=3\text{ auf }(0,0.1213],\qquad T_\alpha(d)=4\text{ auf }(0.7071,0.8],$$
$$T_\alpha(d)=5\text{ auf }(0.4142,0.5071],\qquad T_\alpha(d)=6\text{ auf }(0.1213,0.2142].$$
Dieses Beispiel zeigt genau die Arbeitsweise des Verfahrens: Jeder neue Sprung beansprucht nur noch unbedeckte Startpunkte, und genau diese Segmentanfänge werden später als Events verwendet.
Die C++-, Python- und Java-Implementierungen folgen derselben numerischen Idee. Zuerst werden alle Primzahlen bis \(n\) erzeugt. Danach wird jede Primzahl in die Sprunglänge \(\sqrt{1/p}\) umgewandelt, und für diese Rotation wird die erste Treffzeit auf \([0,1-g]\) segmentweise aufgebaut. Der noch unbedeckte Teil des Bereichs liegt in einer geordneten Intervallstruktur, sodass jeder neue Sprung seine Überlappung exakt abziehen und mit der aktuellen Treffzeit markieren kann.
Nach der Verarbeitung einer Primzahl liegt eine Folge disjunkter Segmente mit konstantem Wert \(\alpha_pT_{\alpha_p}(d)\) vor. Das linke Segment liefert den Anfangswert für die globale Summe; jeder spätere Segmentanfang wird als Ereignis mit dem neuen Primzahlbeitrag gespeichert. Anschließend werden alle Ereignisse sortiert, einmal von links nach rechts durchlaufen und dabei aktuelle Summe sowie bestes Ergebnis aktualisiert.
Eine Implementierung prüft zusätzlich die veröffentlichten Kontrollwerte
$$M(3,0.06)=29.5425,\qquad M(10,0.01)=266.9010$$
bevor der eigentliche Zielfall berechnet wird. Die Python-Version delegiert die schwere numerische Arbeit an denselben kompilierten Kern, daher stimmt ihr Verhalten mit der C++-Variante überein.
Sei \(P=\pi(n)\) die Anzahl der Primzahlen bis \(n\). Für eine feste Primzahl \(p\) sei \(K_p\) die Zahl der untersuchten Sprünge bis zur vollständigen Abdeckung, und \(J_p\) die Zahl der gespeicherten Segmente. Mit einer geordneten Intervallstruktur kostet der Aufbau pro Primzahl in der Praxis ungefähr \(O((K_p+J_p)\log J_p)\). Für
$$E=\sum_{p\le n} J_p$$
Gesamtsegmente benötigt das globale Sortieren \(O(E\log E)\), der Sweep selbst \(O(E)\), und der Speicherverbrauch liegt bei \(O(E+P)\). Effizient ist die Methode, weil sie nur exakte Änderungsstellen verarbeitet und keine feine Abtastung vieler \(d\)-Werte braucht.
Her asal \(p \le n\) için yürüyüşte kullanılan irrasyonel adım uzunluğu
$$\alpha_p=\sqrt{\frac{1}{p}}$$
olarak tanımlanır. Birim çember üzerindeki \(k\)-ıncı konum
$$x_k=\{k\alpha_p\}$$
kesir kısmıdır. Genişliği \(g\) olan boşluk \([d,d+g)\) biçimindedir ve başlangıç noktası \(d\), \(0 \le d \le 1-g\) aralığında değişir. İlk vurma zamanı
$$T_{\alpha_p}(d)=\min\{k\ge 1:x_k\in[d,d+g)\}$$
şeklindedir. İlgili asalın katkısı adım uzunluğu ile ağırlıklandırılır:
$$S(\alpha_p,g,d)=\alpha_p\,T_{\alpha_p}(d).$$
Aranan değer
$$M(n,g)=\max_{0\le d\le 1-g}\sum_{\substack{p\le n\\ p\text{ asal}}} S(\alpha_p,g,d)$$
olur. \(d\) için çok sayıda örnek nokta denemek güvenilir değildir; çünkü gerçek maksimum çok dar bir aralıkta bulunabilir. Bu yüzden çözüm, \(d\)'ye bağlı fonksiyonu tam olarak sonlu sayıda parça-sabit aralığa ayırır ve maksimumu bu temsil üzerinde bulur.
Temel fikir şudur: sabit bir asal için ilk vurma zamanı, yalnızca \(d\) ekseni üzerindeki bazı aralıklarda değişir. Bu aralıklar çıkarıldıktan sonra tüm asalların toplamı bir olay süpürmesiyle tam olarak eniyilenebilir.
Sabit bir asal \(p\) seçip \(\alpha=\alpha_p=\sqrt{1/p}\) yazalım. \(p\) tam kare olmadığı için \(\alpha\) irrasyoneldir. Böylece
$$x_k=\{k\alpha\},\qquad k=1,2,3,\dots,$$
dizisi birim çember üzerinde irrasyonel dönüş oluşturur. Problem açısından önemli olan, her iniş noktasının hangi boşluk başlangıçlarını yakaladığıdır.
\(k\)-ıncı adım boşluğun içine tam olarak şu durumda düşer:
$$x_k\in[d,d+g).$$
Bu eşitsizliği \(d\) açısından çözersek
$$d\le x_k\lt d+g\iff d\in(x_k-g,x_k]$$
elde edilir. Yani her iniş noktası, vurulan boşluk başlangıçları için bir aralık üretir. Geçerli tanım bölgesi ile kesiştirince
$$I_k=(x_k-g,x_k]\cap[0,1-g]$$
aralığı kalır. Uç noktalardaki açık-kapalı tercihler ölçüsü sıfır olan kümeleri etkiler; bu nedenle son maksimumu değiştirmez.
İlk vurma zamanını bulmak için bütün aralıkların birleşimini almak yetmez. Bunun yerine \([0,1-g]\) içinde henüz örtülmemiş kısım tutulur. \(k\)-ıncı adımın ürettiği \(I_k\) aralığı geldiğinde, yalnızca bu aralığın henüz örtülmemiş küme ile kesişimi \(k\) etiketi alır. Daha önce boyanmış noktalar erken vuruldukları için eski etiketlerini korur.
Böylece
$$T_\alpha(d)=k$$
değerinin sabit olduğu ayrık parçalar oluşur. \(\alpha\) irrasyonel olduğundan yörünge modulo \(1\) yoğundur; \(g>0\) sabitken her geçerli başlangıç noktası sonunda vurulur. Tüm alan boyandığı anda daha sonraki sıçramalar ilk vurma zamanını değiştiremez.
İlk vurma parçaları hazır olduğunda asalın katkısı hemen gelir:
$$S(\alpha,g,d)=\alpha\,T_\alpha(d).$$
Dolayısıyla tek bir asalın katkısı da aynı segmentler üzerinde parça-sabittir. Değer yalnızca bu segmentlerin başlangıçlarında değişebilir.
Şunu tanımlayalım:
$$F(d)=\sum_{\substack{p\le n\\ p\text{ asal}}} S(\alpha_p,g,d).$$
Her terim parça-sabit olduğundan \(F(d)\) de parça-sabittir. Toplamın değeri, ancak en az bir asal yeni bir segmente geçtiğinde değişir. Bu yüzden tüm segment başlangıçları olay olarak toplanır, soldan sağa sıralanır ve yürüyen toplam bu olaylar üzerinden güncellenir.
Eğer bir olayda tek bir asalın katkısı \(v_{\text{eski}}\) değerinden \(v_{\text{yeni}}\) değerine geçiyorsa
$$F_{\text{yeni}}=F_{\text{eski}}-v_{\text{eski}}+v_{\text{yeni}}$$
olur. Olaylar arasındaki platoların en büyüğü tam olarak \(M(n,g)\)'yi verir.
Bu durumda geçerli alan \([0,0.8]\)'dir. İlk iniş noktaları
$$x_1\approx 0.7071,\quad x_2\approx 0.4142,\quad x_3\approx 0.1213,\quad x_4\approx 0.8284,\quad x_5\approx 0.5355,\quad x_6\approx 0.2426$$
şeklindedir. Bunların ürettiği ham aralıklar
$$I_1\approx(0.5071,0.7071],\quad I_2\approx(0.2142,0.4142],\quad I_3\approx(0,0.1213],$$
$$I_4\approx(0.6284,0.8],\quad I_5\approx(0.3355,0.5355],\quad I_6\approx(0.0426,0.2426]$$
olur. Daha önce boyanmış parçaları attığımızda
$$T_\alpha(d)=1\text{ on }(0.5071,0.7071],\qquad T_\alpha(d)=2\text{ on }(0.2142,0.4142],$$
$$T_\alpha(d)=3\text{ on }(0,0.1213],\qquad T_\alpha(d)=4\text{ on }(0.7071,0.8],$$
$$T_\alpha(d)=5\text{ on }(0.4142,0.5071],\qquad T_\alpha(d)=6\text{ on }(0.1213,0.2142]$$
elde edilir. Bu küçük örnek, algoritmanın özünü gösterir: her yeni adım yalnızca henüz vurulmamış başlangıçları sahiplenir ve son süpürmede kullanılan olay noktaları tam olarak bu segment başlangıçlarıdır.
C++, Python ve Java uygulamaları aynı sayısal planı izler. Önce \(n\)'ye kadar olan asallar üretilir. Sonra her asal \(\sqrt{1/p}\) adım uzunluğuna dönüştürülür ve o asal için \([0,1-g]\) üzerindeki ilk vurma segmentleri kurulur. Henüz örtülmemiş alan sıralı bir aralık yapısında tutulur; böylece her yeni sıçrama, çakışan kısmı tam olarak kesip ilgili parçalara mevcut vurma zamanını atayabilir.
Bir asal işlendiğinde, elde ayrık segmentler ve bu segmentler üzerindeki sabit \(\alpha_pT_{\alpha_p}(d)\) değeri bulunur. En soldaki segment, alanın başlangıcındaki toplamı kurmak için kullanılır; sonraki her segment başlangıcı ise o asalın yeni değerini taşıyan bir olay haline gelir. Daha sonra bütün olaylar sıralanır, bir kez soldan sağa taranır ve koşan toplam ile görülen en iyi değer güncellenir.
Uygulamalardan biri ayrıca yayınlanmış kontrol değerlerini
$$M(3,0.06)=29.5425,\qquad M(10,0.01)=266.9010$$
doğruladıktan sonra nihai durumu hesaplar. Python sürümü ağır sayısal kısmı aynı derlenmiş çözüme devrettiği için, sayısal davranış C++ sürümü ile aynıdır.
\(P=\pi(n)\), yani \(n\)'ye kadar olan asal sayısı olsun. Sabit bir asal \(p\) için, tüm alan örtülene kadar incelenen sıçrama sayısına \(K_p\), depolanan segment sayısına \(J_p\) diyelim. Sıralı aralık yapısı kullanıldığında asal başına kurulum maliyeti pratikte yaklaşık \(O((K_p+J_p)\log J_p)\) olur. Eğer
$$E=\sum_{p\le n} J_p$$
tüm asalların ürettiği toplam segment sayısıysa, küresel olay sıralaması \(O(E\log E)\), süpürmenin kendisi \(O(E)\), bellek kullanımı ise \(O(E+P)\)'dir. Yöntemin gücü, çok sık bir \(d\) ızgarası denemek yerine yalnızca gerçek değişim noktalarını işlemesidir.
Para cada primo \(p \le n\), el paseo usa la longitud irracional
$$\alpha_p=\sqrt{\frac{1}{p}}.$$
En la circunferencia unitaria, la posición del salto \(k\) es
$$x_k=\{k\alpha_p\}.$$
Se coloca un hueco de anchura \(g\) en \([d,d+g)\), con \(d\) en el dominio válido \(0 \le d \le 1-g\). El primer instante en que el paseo cae dentro del hueco es
$$T_{\alpha_p}(d)=\min\{k\ge 1:x_k\in[d,d+g)\}.$$
La contribución de ese primo se pondera por la propia longitud del salto:
$$S(\alpha_p,g,d)=\alpha_p\,T_{\alpha_p}(d).$$
La cantidad buscada es
$$M(n,g)=\max_{0\le d\le 1-g}\sum_{\substack{p\le n\\ p\text{ primo}}} S(\alpha_p,g,d).$$
Una exploración ingenua de muchos valores de \(d\) no basta, porque el máximo puede aparecer en intervalos muy pequeños. La solución implementada construye la dependencia respecto de \(d\) de forma exacta como una función finita a trozos constante.
La observación central es que, para un primo fijo, el tiempo de primer impacto sólo cambia en ciertos intervalos del eje de \(d\). Una vez que esos intervalos están construidos, la suma sobre todos los primos se maximiza con un barrido sobre puntos de cambio.
Fijemos un primo \(p\) y escribamos \(\alpha=\alpha_p=\sqrt{1/p}\). Como \(p\) no es un cuadrado perfecto, \(\alpha\) es irracional. Entonces
$$x_k=\{k\alpha\},\qquad k=1,2,3,\dots,$$
describe una rotación irracional módulo \(1\). Lo importante para el problema es determinar qué inicios de hueco \(d\) quedan capturados por cada punto de aterrizaje \(x_k\).
El salto \(k\) entra en el hueco exactamente cuando
$$x_k\in[d,d+g).$$
Al despejar \(d\), obtenemos
$$d\le x_k\lt d+g\iff d\in(x_k-g,x_k].$$
Cada punto de aterrizaje pinta, por tanto, un intervalo de posibles comienzos del hueco. Tras intersectarlo con el dominio válido queda
$$I_k=(x_k-g,x_k]\cap[0,1-g].$$
Las diferencias en los extremos sólo afectan a conjuntos de medida cero y no alteran el máximo final.
No basta con unir todos los intervalos \(I_k\). Hay que mantener la parte todavía no cubierta de \([0,1-g]\). Cuando llega el salto \(k\), sólo la intersección entre \(I_k\) y el conjunto descubierto recibe la etiqueta \(k\). Los puntos ya pintados conservan su instante anterior, porque buscamos el primer impacto.
De esta manera se obtiene una partición disjunta en la que
$$T_\alpha(d)=k$$
es constante. Como \(\alpha\) es irracional, la órbita es densa módulo \(1\); con \(g>0\) fijo, todo inicio admisible termina siendo alcanzado. Una vez cubierto todo el dominio, los saltos posteriores ya no pueden modificar \(T_\alpha\).
Con la segmentación del primer impacto ya calculada, la contribución ponderada es
$$S(\alpha,g,d)=\alpha\,T_\alpha(d).$$
Así, para un primo fijo, la función también es constante por tramos. Sólo cambia en los comienzos de los segmentos construidos.
Definimos
$$F(d)=\sum_{\substack{p\le n\\ p\text{ primo}}} S(\alpha_p,g,d).$$
Cada sumando es constante por tramos, luego \(F(d)\) también lo es. El valor global sólo puede cambiar cuando al menos un primo empieza un nuevo segmento. Por eso se recopilan todos esos comienzos como eventos, se ordenan de izquierda a derecha y se recorre la lista manteniendo la suma actual.
Si en un evento la contribución de un primo pasa de \(v_{\text{ant}}\) a \(v_{\text{nuevo}}\), la suma se actualiza mediante
$$F_{\text{nuevo}}=F_{\text{ant}}-v_{\text{ant}}+v_{\text{nuevo}}.$$
El máximo sobre todas las mesetas del barrido es exactamente \(M(n,g)\).
En este caso el dominio admisible es \([0,0.8]\). Los primeros puntos de aterrizaje son
$$x_1\approx 0.7071,\quad x_2\approx 0.4142,\quad x_3\approx 0.1213,\quad x_4\approx 0.8284,\quad x_5\approx 0.5355,\quad x_6\approx 0.2426.$$
Los intervalos brutos correspondientes son
$$I_1\approx(0.5071,0.7071],\quad I_2\approx(0.2142,0.4142],\quad I_3\approx(0,0.1213],$$
$$I_4\approx(0.6284,0.8],\quad I_5\approx(0.3355,0.5355],\quad I_6\approx(0.0426,0.2426].$$
Al eliminar las partes ya cubiertas antes, queda
$$T_\alpha(d)=1\text{ en }(0.5071,0.7071],\qquad T_\alpha(d)=2\text{ en }(0.2142,0.4142],$$
$$T_\alpha(d)=3\text{ en }(0,0.1213],\qquad T_\alpha(d)=4\text{ en }(0.7071,0.8],$$
$$T_\alpha(d)=5\text{ en }(0.4142,0.5071],\qquad T_\alpha(d)=6\text{ en }(0.1213,0.2142].$$
Este ejemplo pequeño reproduce exactamente la lógica de la solución: cada salto nuevo sólo reclama los comienzos del hueco que seguían sin pintar, y esos límites son los eventos usados en el máximo global.
Las implementaciones en C++, Python y Java siguen el mismo esquema numérico. Primero generan todos los primos hasta \(n\). Luego convierten cada primo en la longitud \(\sqrt{1/p}\) y construyen, para ese primo, la descomposición en segmentos del primer impacto sobre \([0,1-g]\). La parte aún descubierta del dominio se guarda en una estructura ordenada de intervalos, lo que permite restar exactamente cada nueva superposición y etiquetar los trozos recién cubiertos con el tiempo actual.
Una vez procesado un primo, ya se conoce una colección disjunta de segmentos y el valor constante \(\alpha_pT_{\alpha_p}(d)\) en cada uno. El segmento más a la izquierda inicializa la suma global en el borde izquierdo del dominio; cada comienzo posterior se almacena como un evento que sustituye la contribución de ese primo. Después, todos los eventos se ordenan, se recorren una sola vez de izquierda a derecha y se actualizan la suma corriente y el mejor valor observado.
Una de las implementaciones también verifica los puntos de control publicados
$$M(3,0.06)=29.5425,\qquad M(10,0.01)=266.9010$$
antes de evaluar el caso final. La versión en Python delega el trabajo numérico pesado al mismo solucionador compilado, por lo que su comportamiento numérico coincide con el de C++.
Sea \(P=\pi(n)\) el número de primos hasta \(n\). Para un primo fijo \(p\), llamemos \(K_p\) al número de saltos examinados hasta cubrir todo el dominio y \(J_p\) al número de segmentos almacenados. Con una estructura ordenada de intervalos, la construcción para un primo cuesta en la práctica alrededor de \(O((K_p+J_p)\log J_p)\). Si
$$E=\sum_{p\le n} J_p$$
es el número total de segmentos entre todos los primos, la ordenación global cuesta \(O(E\log E)\), el barrido cuesta \(O(E)\) y la memoria total es \(O(E+P)\). El ahorro viene de trabajar sólo con puntos de cambio exactos, no con una malla densa de valores candidatos de \(d\).
对每个素数 \(p \le n\)，行走步长取为
$$\alpha_p=\sqrt{\frac{1}{p}}.$$
在单位圆上，第 \(k\) 次落点是
$$x_k=\{k\alpha_p\}.$$
长度为 \(g\) 的缺口放在 \([d,d+g)\) 上，其中起点 \(d\) 满足 \(0 \le d \le 1-g\)。第一次落入缺口的时间定义为
$$T_{\alpha_p}(d)=\min\{k\ge 1:x_k\in[d,d+g)\}.$$
该素数的贡献再乘上步长本身：
$$S(\alpha_p,g,d)=\alpha_p\,T_{\alpha_p}(d).$$
题目要求精确求出
$$M(n,g)=\max_{0\le d\le 1-g}\sum_{\substack{p\le n\\ p\text{ 为素数}}} S(\alpha_p,g,d).$$
如果直接在很多个 \(d\) 上取样，既慢又不可靠，因为最大值可能落在非常狭窄的区间内。实现中的核心思路，是把关于 \(d\) 的函数精确表示成有限个常值区间，然后在这个精确表示上求最大值。
关键观察是：固定一个素数以后，首次命中时间只会在 \(d\)-轴上的某些区间发生变化。只要把这些区间构造出来，所有素数的总和就可以通过一次按事件点排序的扫描精确求出最大值。
先固定一个素数 \(p\)，记 \(\alpha=\alpha_p=\sqrt{1/p}\)。因为 \(p\) 不是完全平方数，所以 \(\alpha\) 是无理数。于是序列
$$x_k=\{k\alpha\},\qquad k=1,2,3,\dots,$$
就是模 \(1\) 的无理旋转轨道。对本题来说，我们并不需要写出闭式公式，而是只关心每个落点 \(x_k\) 会“击中”哪些缺口起点 \(d\)。
第 \(k\) 次跳跃落入缺口，当且仅当
$$x_k\in[d,d+g).$$
把这个不等式改写成 \(d\) 的条件，就得到
$$d\le x_k\lt d+g\iff d\in(x_k-g,x_k].$$
也就是说，每个落点 \(x_k\) 都对应一段可能的缺口起点区间。再与合法定义域相交，就得到
$$I_k=(x_k-g,x_k]\cap[0,1-g].$$
左右端点是否开闭只会影响测度为零的边界点，因此不会改变最后的最大值。
如果只是把所有区间 \(I_k\) 做并集，并不能得到首次命中时间。正确做法是维护 \([0,1-g]\) 中还没有被覆盖的部分。当第 \(k\) 次跳跃产生区间 \(I_k\) 时，只有 \(I_k\) 与“未覆盖集合”的交集才会被赋值为 \(k\)。已经在更早时刻被覆盖的位置，必须保留更小的时间标签，因为我们记录的是第一次命中。
这样就会得到一组互不重叠的区间，在每个区间上都有
$$T_\alpha(d)=k$$
这个常值。由于 \(\alpha\) 是无理数，轨道在模 \(1\) 意义下是稠密的；而 \(g>0\) 固定，所以每一个合法的缺口起点最终都会被某次跳跃击中。一旦整个区间 \([0,1-g]\) 都被着色完毕，后续跳跃就不可能再改变首次命中时间。
一旦首次命中时间的分段结构已经确定，单个素数的贡献就立即可写为
$$S(\alpha,g,d)=\alpha\,T_\alpha(d).$$
因此，对固定素数而言，这个贡献函数在同样的区间上也是常数。它只会在这些区间的起点发生改变。对全局最大值来说，我们只需要保留这些真正的变化位置，而不需要对 \(d\) 做细网格采样。
定义总函数
$$F(d)=\sum_{\substack{p\le n\\ p\text{ 为素数}}} S(\alpha_p,g,d).$$
每一项都是分段常数，所以 \(F(d)\) 自然也是分段常数。它的值只可能在某个素数进入新分段时发生变化。于是我们把所有素数的“分段起点”收集成事件，按从左到右排序，然后扫描整个事件表。
如果某个事件位置上，某一个素数的贡献从 \(v_{\text{old}}\) 变为 \(v_{\text{new}}\)，那么总和只需做一次局部更新：
$$F_{\text{new}}=F_{\text{old}}-v_{\text{old}}+v_{\text{new}}.$$
因为两个相邻事件之间 \(F(d)\) 完全不变，所以扫描过程中每个平台值都是真实候选值，取其中最大者就是精确答案 \(M(n,g)\)。
取 \(\alpha=\sqrt{1/2}\)、\(g=0.2\)，则合法区间是 \([0,0.8]\)。前六个落点近似为
$$x_1\approx 0.7071,\quad x_2\approx 0.4142,\quad x_3\approx 0.1213,\quad x_4\approx 0.8284,\quad x_5\approx 0.5355,\quad x_6\approx 0.2426.$$
对应的原始命中区间为
$$I_1\approx(0.5071,0.7071],\quad I_2\approx(0.2142,0.4142],\quad I_3\approx(0,0.1213],$$
$$I_4\approx(0.6284,0.8],\quad I_5\approx(0.3355,0.5355],\quad I_6\approx(0.0426,0.2426].$$
但首次命中时间不能直接把这些区间原样照搬，因为后来的区间会与更早的区间重叠。把已经覆盖过的部分删掉以后，就得到真正的首次命中分段：
$$T_\alpha(d)=1\text{ 在 }(0.5071,0.7071],\qquad T_\alpha(d)=2\text{ 在 }(0.2142,0.4142],$$
$$T_\alpha(d)=3\text{ 在 }(0,0.1213],\qquad T_\alpha(d)=4\text{ 在 }(0.7071,0.8],$$
$$T_\alpha(d)=5\text{ 在 }(0.4142,0.5071],\qquad T_\alpha(d)=6\text{ 在 }(0.1213,0.2142].$$
这个小例子完整展示了程序的思想：每次新跳跃只“认领”尚未被命中的缺口起点，而最终保留下来的这些分段起点，正是全局扫描中需要排序的事件点。
C++、Python 和 Java 三个实现遵循同一套数值流程。首先生成不超过 \(n\) 的全部素数。然后把每个素数转成步长 \(\sqrt{1/p}\)，并针对这个步长单独构造 \([0,1-g]\) 上的首次命中分段。程序用有序区间结构保存“尚未覆盖”的部分，因此每次新跳跃到来时，都可以精确减去重叠、记录新覆盖片段以及它们对应的首次命中时间。
当某个素数处理完成后，程序就拥有一组互不重叠的区间，以及每个区间上的常值 \(\alpha_pT_{\alpha_p}(d)\)。最左侧区间给出定义域左端的初始总和，后续每个区间起点都变成一条事件记录，表示该素数的当前贡献需要被替换成新的常值。把所有素数的事件合并后排序，再从左到右扫描一次，就能持续更新当前总和与历史最大值。
其中一个实现还会先验证题目给出的两个检查值
$$M(3,0.06)=29.5425,\qquad M(10,0.01)=266.9010$$
再计算最终目标。Python 版本把主要数值计算委托给同一个已编译求解器，因此它与 C++ 版本在数学和数值行为上是一致的。
记 \(P=\pi(n)\) 为不超过 \(n\) 的素数个数。对固定素数 \(p\)，设 \(K_p\) 为覆盖完整定义域前需要检查的跳跃次数，\(J_p\) 为最终保存的首次命中分段数。使用有序区间结构后，单个素数的构造过程在实践中大约是 \(O((K_p+J_p)\log J_p)\)。若
$$E=\sum_{p\le n} J_p$$
表示所有素数总共产生的分段起点数，那么全局排序耗时 \(O(E\log E)\)，线性扫描耗时 \(O(E)\)，总内存约为 \(O(E+P)\)。算法之所以有效，是因为它只处理真正发生变化的位置，而不是在整个 \(d\) 区间上做高密度暴力采样。
Для каждого простого числа \(p \le n\) берётся иррациональная длина шага
$$\alpha_p=\sqrt{\frac{1}{p}}.$$
На единичной окружности \(k\)-я позиция задаётся дробной частью
$$x_k=\{k\alpha_p\}.$$
Щель ширины \(g\) имеет вид \([d,d+g)\), где \(d\) меняется в диапазоне \(0 \le d \le 1-g\). Время первого попадания равно
$$T_{\alpha_p}(d)=\min\{k\ge 1:x_k\in[d,d+g)\}.$$
Вклад данного простого числа умножается на длину шага:
$$S(\alpha_p,g,d)=\alpha_p\,T_{\alpha_p}(d).$$
Требуется найти точное значение
$$M(n,g)=\max_{0\le d\le 1-g}\sum_{\substack{p\le n\\ p\text{ простое}}} S(\alpha_p,g,d).$$
Грубое переборное сканирование по многим значениям \(d\) здесь плохо работает, потому что максимум может лежать на очень узком интервале. Поэтому решение строит функцию от \(d\) точно, как конечную кусочно-постоянную структуру.
Главное наблюдение состоит в том, что для фиксированного простого числа время первого попадания меняется только на некоторых интервалах по \(d\). Если эти интервалы построены, сумму по всем простым можно точно максимизировать одним проходом по точкам изменения.
Зафиксируем простое \(p\) и обозначим \(\alpha=\alpha_p=\sqrt{1/p}\). Так как \(p\) не является квадратом, число \(\alpha\) иррационально. Тогда последовательность
$$x_k=\{k\alpha\},\qquad k=1,2,3,\dots,$$
описывает иррациональное вращение по модулю \(1\). Для задачи важно понять, какие начальные точки щели \(d\) захватывает каждый конкретный момент приземления \(x_k\).
\(k\)-й прыжок попадает внутрь щели тогда и только тогда, когда
$$x_k\in[d,d+g).$$
Если выразить это через \(d\), получаем
$$d\le x_k\lt d+g\iff d\in(x_k-g,x_k].$$
Следовательно, каждый момент приземления задаёт интервал возможных стартов щели. После пересечения с допустимой областью остаётся
$$I_k=(x_k-g,x_k]\cap[0,1-g].$$
Точная обработка крайних точек влияет только на множества меры ноль и не меняет итоговый максимум.
Для вычисления первого времени попадания нельзя просто брать объединение всех интервалов \(I_k\). Нужно хранить ещё не покрытую часть отрезка \([0,1-g]\). Когда приходит интервал \(I_k\), только его пересечение с непокрытым множеством получает метку \(k\). Точки, уже закрашенные раньше, сохраняют более раннее время, потому что нас интересует именно первое попадание.
В результате получается система непересекающихся сегментов, на каждом из которых
$$T_\alpha(d)=k$$
постоянно. Поскольку \(\alpha\) иррационально, орбита плотна по модулю \(1\); при фиксированном \(g>0\) это означает, что любой допустимый старт щели рано или поздно будет достигнут. После полного покрытия области последующие прыжки уже не меняют \(T_\alpha\).
Когда разбиение для первого попадания построено, вклад данного простого числа сразу равен
$$S(\alpha,g,d)=\alpha\,T_\alpha(d).$$
Значит, и эта функция кусочно постоянна на тех же сегментах. Меняться она может только в точках начала сегментов.
Обозначим
$$F(d)=\sum_{\substack{p\le n\\ p\text{ простое}}} S(\alpha_p,g,d).$$
Каждое слагаемое кусочно постоянно, поэтому и \(F(d)\) кусочно постоянно. Сумма может измениться только там, где хотя бы для одного простого начинается новый сегмент. Поэтому все такие начала собираются в общий список событий, сортируются слева направо, и затем выполняется sweep-проход.
Если в некоторой точке вклад одного простого числа меняется с \(v_{\text{old}}\) на \(v_{\text{new}}\), то текущая сумма пересчитывается так:
$$F_{\text{new}}=F_{\text{old}}-v_{\text{old}}+v_{\text{new}}.$$
Максимум по всем плато между соседними событиями и есть точное значение \(M(n,g)\).
Допустимая область здесь равна \([0,0.8]\). Первые точки приземления таковы:
$$x_1\approx 0.7071,\quad x_2\approx 0.4142,\quad x_3\approx 0.1213,\quad x_4\approx 0.8284,\quad x_5\approx 0.5355,\quad x_6\approx 0.2426.$$
Они дают интервалы
$$I_1\approx(0.5071,0.7071],\quad I_2\approx(0.2142,0.4142],\quad I_3\approx(0,0.1213],$$
$$I_4\approx(0.6284,0.8],\quad I_5\approx(0.3355,0.5355],\quad I_6\approx(0.0426,0.2426].$$
Если убрать части, покрытые раньше, то получаем настоящее разбиение для первого попадания:
$$T_\alpha(d)=1\text{ на }(0.5071,0.7071],\qquad T_\alpha(d)=2\text{ на }(0.2142,0.4142],$$
$$T_\alpha(d)=3\text{ на }(0,0.1213],\qquad T_\alpha(d)=4\text{ на }(0.7071,0.8],$$
$$T_\alpha(d)=5\text{ на }(0.4142,0.5071],\qquad T_\alpha(d)=6\text{ на }(0.1213,0.2142].$$
Этот небольшой пример полностью отражает логику алгоритма: каждый новый прыжок захватывает только ещё не покрытые старты щели, а начала итоговых сегментов становятся событиями глобального прохода.
Реализации на C++, Python и Java следуют одному и тому же численному плану. Сначала они строят список всех простых чисел до \(n\). Затем каждое простое число превращается в длину шага \(\sqrt{1/p}\), и для этой длины отдельно строится сегментация функции первого попадания на \([0,1-g]\). Ещё не покрытая часть области хранится в упорядоченной интервальной структуре, поэтому каждый новый прыжок может точно вырезать своё пересечение и присвоить новым кускам текущий номер прыжка.
После обработки одного простого числа известны непересекающиеся сегменты и постоянное значение \(\alpha_pT_{\alpha_p}(d)\) на каждом из них. Самый левый сегмент задаёт начальную сумму в левой точке области, а каждое последующее начало сегмента превращается в событие, которое заменяет текущий вклад этого простого числа на новый. После этого все события сортируются, один раз просматриваются слева направо, и при этом обновляются текущая сумма и наилучшее найденное значение.
Одна из реализаций дополнительно проверяет опубликованные контрольные значения
$$M(3,0.06)=29.5425,\qquad M(10,0.01)=266.9010$$
перед вычислением финального случая. В Python тяжёлая численная часть делегируется тому же скомпилированному решателю, поэтому численное поведение совпадает с версией на C++.
Пусть \(P=\pi(n)\) обозначает число простых, не превосходящих \(n\). Для фиксированного простого \(p\) обозначим через \(K_p\) число проверенных прыжков до полного покрытия области, а через \(J_p\) число сохранённых сегментов. При использовании упорядоченной интервальной структуры построение для одного простого в практическом смысле стоит примерно \(O((K_p+J_p)\log J_p)\). Если
$$E=\sum_{p\le n} J_p$$
это общее число сегментов по всем простым, тогда сортировка всех событий стоит \(O(E\log E)\), сам sweep-проход стоит \(O(E)\), а память равна \(O(E+P)\). Метод выигрывает за счёт того, что работает только с точными точками изменения, а не с плотной сеткой кандидатов для \(d\).
لكل عدد أولي \(p \le n\)، يكون طول القفزة غير النسبي
$$\alpha_p=\sqrt{\frac{1}{p}}.$$
وعلى دائرة الوحدة تكون نقطة الوصول بعد القفزة رقم \(k\) هي
$$x_k=\{k\alpha_p\}.$$
نضع فجوة طولها \(g\) على الصورة \([d,d+g)\)، حيث يتحرك \(d\) داخل المجال \(0 \le d \le 1-g\). زمن أول إصابة هو
$$T_{\alpha_p}(d)=\min\{k\ge 1:x_k\in[d,d+g)\}.$$
ثم يوزن إسهام هذا العدد الأولي بطول القفزة نفسه:
$$S(\alpha_p,g,d)=\alpha_p\,T_{\alpha_p}(d).$$
والمطلوب هو إيجاد
$$M(n,g)=\max_{0\le d\le 1-g}\sum_{\substack{p\le n\\ p\text{ prime}}} S(\alpha_p,g,d).$$
التجريب العددي لكثير من قيم \(d\) لا يكفي هنا، لأن القيمة العظمى قد تظهر على فاصل صغير جدًا. لذلك تبني الخوارزمية الدالة بدلالة \(d\) بناءً دقيقًا على هيئة عدد من المقاطع الثابتة، ثم تبحث عن القيمة العظمى على هذه البنية نفسها.
الفكرة الأساسية هي أن زمن أول إصابة، عند تثبيت عدد أولي واحد، لا يتغير إلا على فواصل معينة على محور \(d\). وبعد استخراج هذه الفواصل يمكن تعظيم مجموع جميع الإسهامات بواسطة مسح واحد على نقاط التغير.
لنثبت عددًا أوليًا \(p\) ونكتب \(\alpha=\alpha_p=\sqrt{1/p}\). بما أن \(p\) ليس مربعًا كاملاً، فإن \(\alpha\) عدد غير نسبي. لذلك فإن المتتالية
$$x_k=\{k\alpha\},\qquad k=1,2,3,\dots,$$
تمثل دورانًا لا نسبيًا بترديد \(1\). ما يهمنا في هذه المسألة هو معرفة أي بدايات \(d\) للفجوة تصيبها نقطة الهبوط \(x_k\).
تدخل القفزة رقم \(k\) داخل الفجوة إذا وفقط إذا تحقق
$$x_k\in[d,d+g).$$
وبحل هذا الشرط بالنسبة إلى \(d\) نحصل على
$$d\le x_k\lt d+g\iff d\in(x_k-g,x_k].$$
إذن كل نقطة هبوط تولد فاصلًا من قيم البداية الممكنة. وبعد تقاطعه مع المجال المسموح يبقى
$$I_k=(x_k-g,x_k]\cap[0,1-g].$$
اختيار الطرف المفتوح أو المغلق لا يؤثر إلا في نقاط حدية ذات قياس صفري، ولذلك لا يغير القيمة العظمى النهائية.
ليس كافيًا أن نأخذ اتحاد جميع الفواصل \(I_k\). المطلوب هو زمن أول إصابة، ولهذا نحافظ على الجزء غير المغطى بعد من \([0,1-g]\). عندما تصل القفزة رقم \(k\) وتعطي الفاصل \(I_k\)، فإن الجزء الوحيد الذي يحصل على القيمة \(k\) هو التقاطع بين \(I_k\) وبين الجزء غير المغطى. أما النقاط التي غطيت سابقًا فتبقى محتفظة بزمنها الأصغر.
بهذا نحصل على مجموعة فواصل متباينة يكون عليها
$$T_\alpha(d)=k$$
ثابتًا. وبما أن \(\alpha\) غير نسبي فإن المدار كثيف بترديد \(1\)، ومع ثبات \(g>0\) فهذا يعني أن كل بداية صالحة للفجوة ستصاب في النهاية. وما إن يكتمل تغطية المجال حتى تصبح القفزات اللاحقة عديمة الأثر على زمن أول إصابة.
بعد معرفة تقطيع زمن أول إصابة، يصبح إسهام ذلك العدد الأولي مباشرة
$$S(\alpha,g,d)=\alpha\,T_\alpha(d).$$
ولذلك تكون هذه الدالة أيضًا ثابتة على كل قطعة من القطع نفسها. أما نقاط التغير فلا تظهر إلا عند بدايات تلك القطع.
لنعرّف
$$F(d)=\sum_{\substack{p\le n\\ p\text{ prime}}} S(\alpha_p,g,d).$$
كل حد في هذا المجموع دالة مقطعية ثابتة، ولذلك فإن \(F(d)\) كذلك. لا يمكن أن تتغير قيمة \(F(d)\) إلا عندما يبدأ أحد الأعداد الأولية قطعة جديدة. لهذا السبب تُجمع جميع بدايات القطع في قائمة أحداث، ثم ترتب من اليسار إلى اليمين ويجرى عليها مسح متتابع.
إذا تغير إسهام أحد الأعداد الأولية عند حدث ما من \(v_{\text{old}}\) إلى \(v_{\text{new}}\)، فإن التحديث المحلي للمجموع هو
$$F_{\text{new}}=F_{\text{old}}-v_{\text{old}}+v_{\text{new}}.$$
وبما أن \(F(d)\) يبقى ثابتًا بين كل حدثين متتاليين، فإن أكبر منصة تظهر أثناء المسح تعطي القيمة الدقيقة لـ \(M(n,g)\).
خذ \(\alpha=\sqrt{1/2}\) و\(g=0.2\). عندئذ يكون المجال المسموح هو \([0,0.8]\). أوائل نقاط الهبوط هي
$$x_1\approx 0.7071,\quad x_2\approx 0.4142,\quad x_3\approx 0.1213,\quad x_4\approx 0.8284,\quad x_5\approx 0.5355,\quad x_6\approx 0.2426.$$
ومنها تنتج الفواصل الخام
$$I_1\approx(0.5071,0.7071],\quad I_2\approx(0.2142,0.4142],\quad I_3\approx(0,0.1213],$$
$$I_4\approx(0.6284,0.8],\quad I_5\approx(0.3355,0.5355],\quad I_6\approx(0.0426,0.2426].$$
لكننا لا نأخذ هذه الفواصل كما هي، بل نحذف كل جزء غطي سابقًا. بعد ذلك تصبح دالة أول إصابة
$$T_\alpha(d)=1,\quad d\in(0.5071,0.7071],\qquad T_\alpha(d)=2,\quad d\in(0.2142,0.4142],$$
$$T_\alpha(d)=3,\quad d\in(0,0.1213],\qquad T_\alpha(d)=4,\quad d\in(0.7071,0.8],$$
$$T_\alpha(d)=5,\quad d\in(0.4142,0.5071],\qquad T_\alpha(d)=6,\quad d\in(0.1213,0.2142].$$
هذا المثال الصغير يوضح الفكرة كاملة: كل قفزة جديدة تستولي فقط على بدايات الفجوات التي ما زالت غير مغطاة، وبدايات القطع النهائية هي نفسها نقاط الأحداث التي يعتمد عليها المسح العام.
تتبع تطبيقات ++C وPython وJava الخطة العددية نفسها. أولًا تُولَّد جميع الأعداد الأولية حتى \(n\). ثم يتحول كل عدد أولي إلى طول الخطوة \(\sqrt{1/p}\)، وتبنى له على حدة المقاطع التي تصف زمن أول إصابة على المجال \([0,1-g]\). ويُحفظ الجزء غير المغطى في بنية مرتبة من الفواصل، مما يسمح لكل قفزة جديدة بأن تخصم تقاطعها بدقة وتسجل الأجزاء التي غطتها للمرة الأولى.
بعد إنهاء عدد أولي واحد، يصبح لدينا عدد من المقاطع المتباينة والقيمة الثابتة \(\alpha_pT_{\alpha_p}(d)\) على كل مقطع. المقطع الأيسر يحدد القيمة الابتدائية للمجموع عند بداية المجال، وكل بداية لاحقة لمقطع جديد تتحول إلى حدث يستبدل الإسهام الحالي لذلك العدد الأولي بقيمة جديدة. بعد ذلك تُجمع كل الأحداث، وتُرتب، ويجرى عليها مرور واحد من اليسار إلى اليمين لتحديث المجموع الجاري وأفضل قيمة شوهدت.
كما أن أحد التطبيقات يتحقق أولًا من قيمتي الفحص المنشورتين
$$M(3,0.06)=29.5425,\qquad M(10,0.01)=266.9010$$
قبل حساب الحالة النهائية. أما نسخة Python فتعتمد في الحسابات الثقيلة على نفس المحرك المترجم، ولذلك تتطابق عدديًا مع تطبيق ++C.
ليكن \(P=\pi(n)\) عدد الأعداد الأولية حتى \(n\). وبالنسبة إلى عدد أولي ثابت \(p\)، لِنرمز بـ \(K_p\) إلى عدد القفزات التي تُفحص حتى يغطى المجال كله، وبـ \(J_p\) إلى عدد المقاطع التي تُخزن فعليًا. باستخدام بنية مرتبة للفواصل تكون كلفة المعالجة لذلك العدد الأولي تقريبًا \(O((K_p+J_p)\log J_p)\) عمليًا. وإذا كان
$$E=\sum_{p\le n} J_p$$
هو العدد الكلي لبدايات المقاطع عبر جميع الأعداد الأولية، فإن فرز الأحداث يكلف \(O(E\log E)\)، بينما يكلف المسح نفسه \(O(E)\)، وتكون الذاكرة \(O(E+P)\). وتكمن فعالية الطريقة في أنها تتعامل مع نقاط التغير الحقيقية فقط، بدلًا من اختبار شبكة كثيفة من القيم المرشحة لـ \(d\).