Take the consecutive primes \(p_1,p_2,p_3,\dots\) and pair them as \((p_1,p_2),(p_3,p_4),\dots\). Starting from \((0,0)\), move upward with slope \(+1\) for horizontal distance \(p_{2k-1}\), then downward with slope \(-1\) for horizontal distance \(p_{2k}\). The endpoint of the upward segment in the \(k\)-th pair is peak \(k\).
For each peak \(k\), define \(P(k)\) as the number of earlier peaks that are visible from \(k\): a peak \(j\lt k\) is visible if the segment joining peaks \(j\) and \(k\) stays strictly above every intermediate peak. The task is to compute
$$\sum_{k=1}^{N} P(k),\qquad N=2{,}500{,}000.$$
The implemented method turns visibility into an ordered slope problem. Once that reformulation is in place, the search can be pruned with upper convex hull information for prefixes of the peak sequence.
Let \((x_k,y_k)\) be the coordinates of peak \(k\). The construction gives
$$x_k=\sum_{i=1}^{2k-1} p_i,$$
because \(x\) advances by every prime used so far until the top of the \(k\)-th ascent. Likewise, the height is
$$y_k=\sum_{i=1}^{2k-1} (-1)^{i+1} p_i,$$
since odd-indexed primes raise the mountain range and even-indexed primes lower it again. In particular,
$$x_1 \lt x_2 \lt x_3 \lt \cdots,$$
so every visibility question is a comparison between slopes from a fixed right endpoint to points with smaller \(x\)-coordinate.
Fix a peak \(k\) and define the slope from peak \(j\) to peak \(k\) by
$$s_k(j)=\frac{y_k-y_j}{x_k-x_j},\qquad 1\le j\lt k.$$
Now take an intermediate peak \(i\) with \(j\lt i\lt k\). The point \(i\) lies strictly below the chord from \(j\) to \(k\) exactly when
$$y_i \lt y_k-\frac{y_k-y_j}{x_k-x_j}(x_k-x_i).$$
After rearranging, this becomes
$$\frac{y_k-y_i}{x_k-x_i} \gt \frac{y_k-y_j}{x_k-x_j},$$
or in the new notation, \(s_k(i)\gt s_k(j)\). Therefore peak \(j\) is visible from peak \(k\) if and only if
$$s_k(j)\lt s_k(i)\qquad\text{for every }i\text{ with }j\lt i\lt k.$$
So when we scan \(j=k-1,k-2,\dots,1\), the visible peaks are exactly the indices where the slope becomes a new strict minimum. The nearest peak \(k-1\) is always visible, because there is no intermediate peak between \(k-1\) and \(k\).
The coordinates become large, so dividing two integers and comparing floating-point values would be risky. Because all denominators are positive, slope comparisons can be rewritten as
$$s_k(j_1)\lt s_k(j_2)\iff (y_k-y_{j_1})(x_k-x_{j_2}) \lt (y_k-y_{j_2})(x_k-x_{j_1}).$$
This is mathematically exact and avoids rounding error. The compiled implementations use wide integer arithmetic for these cross-products, so the visibility test remains exact even at the full problem size.
Suppose the current visible peak for the scan of peak \(k\) is \(b\). Any next visible peak must lie somewhere in the prefix \(\{1,2,\dots,b-1\}\). For a fixed right endpoint \(k\), the minimum of \(s_k(j)\) over that prefix is attained on the upper convex hull of the prefix, not at an interior point below the hull.
Geometrically, when a line through peak \(k\) rotates downward, the first point of the prefix that it can touch is a vertex of the upper hull. Therefore:
$$\exists\, j\lt b\text{ with }s_k(j)\lt s_k(b)\iff \exists\, v\text{ on the upper hull of }\{1,\dots,b-1\}\text{ with }s_k(v)\lt s_k(b).$$
This does not immediately identify the next visible peak, but it gives a fast existence test. If no upper-hull vertex improves the slope, the scan can stop at once.
The first nine peaks come from the primes \(2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61\). Their coordinates are
$$\begin{aligned} (x_1,y_1)&=(2,2),\\ (x_2,y_2)&=(10,4),\\ (x_3,y_3)&=(28,8),\\ (x_4,y_4)&=(58,12),\\ (x_5,y_5)&=(100,16),\\ (x_6,y_6)&=(160,18),\\ (x_7,y_7)&=(238,22),\\ (x_8,y_8)&=(328,26),\\ (x_9,y_9)&=(440,32). \end{aligned}$$
For \(k=9\), the slopes to earlier peaks are
$$\begin{aligned} s_9(8)&=\frac{32-26}{440-328}=\frac{6}{112},\\ s_9(7)&=\frac{32-22}{440-238}=\frac{10}{202},\\ s_9(6)&=\frac{14}{280},\\ s_9(5)&=\frac{16}{340},\\ s_9(4)&=\frac{20}{382},\\ s_9(3)&=\frac{24}{412},\\ s_9(2)&=\frac{28}{430},\\ s_9(1)&=\frac{30}{438}. \end{aligned}$$
Scanning from right to left, the record-low slopes occur at \(j=8\), then \(j=7\), then \(j=5\). Hence
$$P(9)=3.$$
The same method gives \(P(3)=1\), and the cumulative value
$$\sum_{k=1}^{100} P(k)=227$$
matches the checkpoints used by the optimized implementation.
The C++, Python, and Java implementations all rely on the same geometry. First, they generate the first \(2N\) primes with an odd-only sieve large enough to cover the required range. Then they build the peak coordinates in a single pass by pairing consecutive primes into one ascent and one descent.
During that same left-to-right pass, the compiled implementations maintain the upper hull of every prefix with a monotone stack. When a new point arrives, the previous hull vertex is removed while the last three hull points fail to form a strict upper turn. The remaining predecessor link is stored so that the upper hull of any prefix can later be traversed backward in constant extra memory per point.
To compute \(P(k)\), the implementation starts with peak \(k-1\), which is automatically visible. It then repeatedly asks whether the earlier prefix contains any point with a smaller slope than the current visible peak. That question is answered by walking only along the stored upper-hull chain of the prefix. If the answer is no, the search ends. If the answer is yes, the implementation walks left until it reaches the first index whose slope is smaller than the current best; that index is the next visible peak, and the process repeats.
The C++ version also checks the first small range against a direct full scan and known checkpoint totals before launching the production run. The C++ and Java versions split the remaining \(k\)-values across several worker threads and add the partial sums. The Python implementation does not reimplement the geometry in pure Python; it delegates to the compiled optimized solver and returns the resulting numeric answer.
Let \(M\) be the sieve limit used to obtain the first \(2N\) primes; in the implementation this is a fixed bound large enough for \(N=2{,}500{,}000\). The sieve costs \(O(M\log\log M)\) time and \(O(M)\) memory in its chosen representation, while building coordinates and prefix hull links costs \(O(N)\) time and \(O(N)\) memory. A direct visibility scan over all pairs of peaks would be \(O(N^2)\). The implemented method keeps the same \(O(N)\) storage for geometric data but prunes most searches through upper-hull existence tests, making the actual Project Euler instance tractable. The code does not present a formal worst-case bound better than quadratic for the search phase, so the honest claim is strong practical acceleration rather than a proved asymptotic improvement.
Man nimmt die aufeinanderfolgenden Primzahlen \(p_1,p_2,p_3,\dots\) und gruppiert sie zu Paaren \((p_1,p_2),(p_3,p_4),\dots\). Vom Punkt \((0,0)\) aus geht man mit Steigung \(+1\) um die horizontale Distanz \(p_{2k-1}\) nach oben und anschließend mit Steigung \(-1\) um die Distanz \(p_{2k}\) wieder nach unten. Der Endpunkt des Aufstiegs im \(k\)-ten Paar ist der \(k\)-te Gipfel.
Für jeden Gipfel \(k\) sei \(P(k)\) die Anzahl früherer Gipfel, die von \(k\) aus sichtbar sind: Ein Gipfel \(j\lt k\) ist sichtbar, wenn das Verbindungssegment zwischen \(j\) und \(k\) strikt oberhalb aller dazwischenliegenden Gipfel verläuft. Gesucht ist
$$\sum_{k=1}^{N} P(k),\qquad N=2{,}500{,}000.$$
Die implementierte Lösung formt die Sichtbarkeitsbedingung in ein Problem über geordnete Steigungen um. Anschließend wird die Suche mit Informationen über die obere konvexe Hülle von Präfixen der Gipfelfolge stark beschnitten.
Sei \((x_k,y_k)\) der \(k\)-te Gipfel. Aus der Konstruktion folgt
$$x_k=\sum_{i=1}^{2k-1} p_i,$$
denn bis zur Spitze des \(k\)-ten Aufstiegs wurden genau diese Primzahlen als horizontale Schritte verbraucht. Für die Höhe gilt
$$y_k=\sum_{i=1}^{2k-1} (-1)^{i+1} p_i,$$
weil Primzahlen mit ungeradem Index den Gebirgszug anheben und Primzahlen mit geradem Index ihn wieder absenken. Insbesondere ist
$$x_1 \lt x_2 \lt x_3 \lt \cdots,$$
also jede Sichtbarkeitsfrage ein Vergleich von Steigungen zu einem festen rechten Endpunkt.
Fixiere einen Gipfel \(k\) und definiere
$$s_k(j)=\frac{y_k-y_j}{x_k-x_j},\qquad 1\le j\lt k.$$
Für einen Zwischenpunkt \(i\) mit \(j\lt i\lt k\) liegt \(i\) genau dann strikt unterhalb der Sehne von \(j\) nach \(k\), wenn
$$y_i \lt y_k-\frac{y_k-y_j}{x_k-x_j}(x_k-x_i).$$
Nach Umformen erhält man
$$\frac{y_k-y_i}{x_k-x_i} \gt \frac{y_k-y_j}{x_k-x_j},$$
also \(s_k(i)\gt s_k(j)\). Damit ist Gipfel \(j\) von \(k\) aus genau dann sichtbar, wenn
$$s_k(j)\lt s_k(i)\qquad\text{für alle }i\text{ mit }j\lt i\lt k.$$
Beim Scan \(j=k-1,k-2,\dots,1\) sind die sichtbaren Gipfel somit genau die Stellen, an denen die Steigung ein neues striktes Minimum erreicht. Der Nachbar \(k-1\) ist immer sichtbar, weil es zwischen \(k-1\) und \(k\) keinen weiteren Gipfel gibt.
Die Koordinaten werden groß, daher wäre ein Vergleich per Fließkommadivision unnötig riskant. Weil alle Nenner positiv sind, gilt äquivalent
$$s_k(j_1)\lt s_k(j_2)\iff (y_k-y_{j_1})(x_k-x_{j_2}) \lt (y_k-y_{j_2})(x_k-x_{j_1}).$$
Das ist exakt und vermeidet Rundungsfehler vollständig. Die kompilierten Implementierungen benutzen für diese Kreuzprodukte breite Ganzzahlarithmetik, sodass der Sichtbarkeitstest auch bei der vollen Problemgröße präzise bleibt.
Angenommen, der aktuell sichtbare Gipfel beim Scan für \(k\) ist \(b\). Dann muss der nächste sichtbare Gipfel in dem Präfix \(\{1,2,\dots,b-1\}\) liegen. Für einen festen rechten Endpunkt \(k\) wird das Minimum von \(s_k(j)\) über diesem Präfix auf der oberen konvexen Hülle angenommen, nicht an einem inneren Punkt unterhalb der Hülle.
Geometrisch heißt das: Wenn man eine Gerade durch Gipfel \(k\) nach unten dreht, ist der erste Berührpunkt mit dem Präfix ein Eckpunkt der oberen Hülle. Also gilt
$$\exists\, j\lt b\text{ mit }s_k(j)\lt s_k(b)\iff \exists\, v\text{ auf der oberen Hülle von }\{1,\dots,b-1\}\text{ mit }s_k(v)\lt s_k(b).$$
Damit kennt man den nächsten sichtbaren Gipfel noch nicht direkt, aber man erhält einen schnellen Existenztest. Wenn kein Hüllenpunkt die Steigung verbessert, kann der Scan sofort enden.
Die ersten neun Gipfel entstehen aus den Primzahlen \(2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61\). Ihre Koordinaten sind
$$\begin{aligned} (x_1,y_1)&=(2,2),\\ (x_2,y_2)&=(10,4),\\ (x_3,y_3)&=(28,8),\\ (x_4,y_4)&=(58,12),\\ (x_5,y_5)&=(100,16),\\ (x_6,y_6)&=(160,18),\\ (x_7,y_7)&=(238,22),\\ (x_8,y_8)&=(328,26),\\ (x_9,y_9)&=(440,32). \end{aligned}$$
Für \(k=9\) lauten die Steigungen zu den früheren Gipfeln
$$\begin{aligned} s_9(8)&=\frac{6}{112},\\ s_9(7)&=\frac{10}{202},\\ s_9(6)&=\frac{14}{280},\\ s_9(5)&=\frac{16}{340},\\ s_9(4)&=\frac{20}{382},\\ s_9(3)&=\frac{24}{412},\\ s_9(2)&=\frac{28}{430},\\ s_9(1)&=\frac{30}{438}. \end{aligned}$$
Beim Scan von rechts nach links treten neue Minimalwerte bei \(j=8\), dann \(j=7\) und schließlich \(j=5\) auf. Also ist
$$P(9)=3.$$
Ebenso ergibt sich \(P(3)=1\), und der Kontrollwert
$$\sum_{k=1}^{100} P(k)=227$$
stimmt mit den Prüfpunkten der Implementierung überein.
Die C++-, Python- und Java-Implementierungen basieren auf derselben Geometrie. Zuerst werden die ersten \(2N\) Primzahlen mit einem Sieb für ungerade Zahlen erzeugt. Danach werden die Gipfelkoordinaten in einem einzigen Durchlauf aufgebaut, indem jeweils zwei aufeinanderfolgende Primzahlen einen Aufstieg und einen Abstieg bilden.
Während dieses Links-nach-rechts-Durchlaufs pflegen die kompilierten Implementierungen zugleich die obere Hülle jedes Präfixes mit einem monotonen Stack. Kommt ein neuer Punkt hinzu, wird der vorherige Hüllenpunkt entfernt, solange die letzten drei Hüllenpunkte keine strikte obere Drehung bilden. Der verbleibende Vorgänger wird gespeichert, sodass sich die obere Hülle jedes Präfixes später rückwärts mit konstantem Zusatzspeicher pro Punkt traversieren lässt.
Zur Berechnung von \(P(k)\) startet die Implementierung bei Gipfel \(k-1\), der automatisch sichtbar ist. Anschließend wird wiederholt gefragt, ob das frühere Präfix irgendeinen Punkt mit kleinerer Steigung als der aktuelle sichtbare Gipfel enthält. Diese Frage wird beantwortet, indem nur die gespeicherte Hüllenkette des Präfixes durchlaufen wird. Falls kein Hüllenpunkt die Steigung verbessert, endet die Suche. Falls doch, läuft die Implementierung nach links, bis sie den ersten Index mit kleinerer Steigung findet; dieser Index ist der nächste sichtbare Gipfel, und der Vorgang wiederholt sich.
Die C++-Version vergleicht den ersten kleinen Bereich zusätzlich mit einem direkten Vollscan und bekannten Kontrollsummen, bevor die eigentliche Rechnung startet. C++ und Java teilen den verbleibenden Bereich der \(k\)-Werte auf mehrere Worker-Threads auf und addieren die Teilsummen. Die Python-Implementierung programmiert die Geometrie nicht separat in reinem Python nach, sondern delegiert an den kompilierten optimierten Solver und liefert dessen numerisches Ergebnis zurück.
Sei \(M\) die Siebgrenze, die benötigt wird, um die ersten \(2N\) Primzahlen zu erhalten; in der Implementierung ist das eine feste Schranke, die für \(N=2{,}500{,}000\) ausreicht. Das Sieb kostet \(O(M\log\log M)\) Zeit und \(O(M)\) Speicher in der gewählten Darstellung. Der Aufbau von Koordinaten und Präfix-Hüllenlinks kostet \(O(N)\) Zeit und \(O(N)\) Speicher. Ein direkter Sichtbarkeitsscan über alle Gipfelpaare wäre \(O(N^2)\). Die implementierte Methode behält \(O(N)\) geometrischen Speicher bei und schneidet den Suchraum durch Hüllen-Existenztests stark zurück, sodass der konkrete Project-Euler-Fall praktisch berechenbar wird. Der Code liefert jedoch keinen formalen Worst-Case-Beweis unterhalb von quadratischer Zeit für die Suchphase; mathematisch sauber ist also die Aussage einer starken praktischen Beschleunigung, nicht einer bewiesenen asymptotischen Schranke.
Ardışık asal sayıları \(p_1,p_2,p_3,\dots\) alıp bunları \((p_1,p_2),(p_3,p_4),\dots\) çiftleri halinde gruplayalım. \((0,0)\) noktasından başlayıp yatay uzunluğu \(p_{2k-1}\) olan, eğimi \(+1\) olan bir çıkış yapılıyor; sonra yatay uzunluğu \(p_{2k}\) olan, eğimi \(-1\) olan bir iniş geliyor. \(k\)-ıncı çiftteki çıkışın bittiği nokta \(k\)-ıncı zirvedir.
Her \(k\) zirvesi için \(P(k)\), soldaki görünür zirvelerin sayısı olsun: \(j\lt k\) olan bir zirve, \(j\) ile \(k\) arasındaki doğru parçası aradaki bütün zirvelerin kesin olarak üstünde kalıyorsa görünür sayılır. Hesaplanması istenen toplam
$$\sum_{k=1}^{N} P(k),\qquad N=2{,}500{,}000$$
ifadesidir.
Uygulanan yöntem görünürlük koşulunu sıralı eğim karşılaştırmalarına dönüştürür. Bu dönüşümden sonra, zirve dizisinin prefix'leri için tutulan üst konveks zarf bilgisi aramayı ciddi biçimde budar.
\((x_k,y_k)\) \(k\)-ıncı zirvenin koordinatları olsun. Kurulumdan doğrudan
$$x_k=\sum_{i=1}^{2k-1} p_i$$
elde edilir; çünkü \(k\)-ıncı çıkışın tepesine gelene kadar kullanılan yatay adımlar tam olarak bu asallardır. Yükseklik de
$$y_k=\sum_{i=1}^{2k-1} (-1)^{i+1} p_i$$
şeklindedir; tek indeksli asallar yüksekliği artırır, çift indeksli asallar azaltır. Özellikle
$$x_1 \lt x_2 \lt x_3 \lt \cdots$$
olduğu için, her görünürlük sorusu sabit bir sağ uçtan daha soldaki noktalara giden eğimlerin karşılaştırılmasına indirgenir.
Sabit bir \(k\) zirvesi için
$$s_k(j)=\frac{y_k-y_j}{x_k-x_j},\qquad 1\le j\lt k$$
tanımını yapalım. \(j\lt i\lt k\) olan bir ara zirve \(i\), \(j\) ile \(k\) arasındaki kirişin altında tam olarak şu durumda kalır:
$$y_i \lt y_k-\frac{y_k-y_j}{x_k-x_j}(x_k-x_i).$$
Düzenleyince
$$\frac{y_k-y_i}{x_k-x_i} \gt \frac{y_k-y_j}{x_k-x_j}$$
elde edilir; yani \(s_k(i)\gt s_k(j)\). Demek ki \(j\) zirvesi, \(k\) zirvesinden ancak ve ancak
$$s_k(j)\lt s_k(i)\qquad\text{her }j\lt i\lt k\text{ için}$$
ise görünürdür. Bu nedenle \(j=k-1,k-2,\dots,1\) şeklinde sağdan sola tarama yapıldığında görünür zirveler, eğimin yeni bir kesin minimum olduğu indekslerdir. En yakın zirve \(k-1\) her zaman görünürdür; çünkü arada başka zirve yoktur.
Koordinatlar büyüdüğü için kayan nokta bölmeleri gereksiz hata riski taşır. Paydalar pozitif olduğundan
$$s_k(j_1)\lt s_k(j_2)\iff (y_k-y_{j_1})(x_k-x_{j_2}) \lt (y_k-y_{j_2})(x_k-x_{j_1})$$
eşdeğerliği kullanılabilir. Böylece görünürlük testi tamamen tam sayılarla ve hatasız yapılır. Derlenmiş uygulamalar bu çapraz çarpımları geniş tamsayı aritmetiğiyle hesaplar.
\(k\) için taramada mevcut görünür zirve \(b\) olsun. Bir sonraki görünür zirve mutlaka \(\{1,2,\dots,b-1\}\) prefix'inde bulunur. Sabit sağ uç \(k\) için, bu prefix üzerinde \(s_k(j)\) ifadesinin minimumu iç noktada değil, üst konveks zarfın bir köşesinde gerçekleşir.
Geometrik olarak, \(k\) noktasından geçen bir doğru aşağıya döndürülürse prefix'e ilk değen nokta üst zarfın bir köşesidir. Dolayısıyla
$$\exists\, j\lt b\text{ öyle ki }s_k(j)\lt s_k(b)\iff \exists\, v\text{, }\{1,\dots,b-1\}\text{ üst zarfında ve }s_k(v)\lt s_k(b).$$
Bu test bir sonraki görünür zirveyi doğrudan vermez, fakat çok hızlı bir "daha iyi aday var mı?" sorgusu sağlar. Üst zarf üzerinde iyileşme yoksa tarama anında durdurulur.
İlk dokuz zirve \(2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61\) asallarından gelir. Koordinatlar
$$\begin{aligned} (x_1,y_1)&=(2,2),\\ (x_2,y_2)&=(10,4),\\ (x_3,y_3)&=(28,8),\\ (x_4,y_4)&=(58,12),\\ (x_5,y_5)&=(100,16),\\ (x_6,y_6)&=(160,18),\\ (x_7,y_7)&=(238,22),\\ (x_8,y_8)&=(328,26),\\ (x_9,y_9)&=(440,32). \end{aligned}$$
\(k=9\) için önceki zirvelere giden eğimler
$$\begin{aligned} s_9(8)&=\frac{6}{112},\\ s_9(7)&=\frac{10}{202},\\ s_9(6)&=\frac{14}{280},\\ s_9(5)&=\frac{16}{340},\\ s_9(4)&=\frac{20}{382},\\ s_9(3)&=\frac{24}{412},\\ s_9(2)&=\frac{28}{430},\\ s_9(1)&=\frac{30}{438}. \end{aligned}$$
Sağdan sola taramada yeni minimumlar sırasıyla \(j=8\), sonra \(j=7\), sonra \(j=5\) olur. Bu yüzden
$$P(9)=3.$$
Aynı yöntem \(P(3)=1\) sonucunu verir ve
$$\sum_{k=1}^{100} P(k)=227$$
değeri uygulamadaki kontrol noktalarıyla tam uyuşur.
C++, Python ve Java uygulamalarının geometrik çekirdeği aynıdır. Önce, gerekli ilk \(2N\) asal sayıyı elde etmek için sadece tek sayıları tutan bir elek kurulur. Ardından zirve koordinatları tek geçişte üretilir; her ardışık iki asal, bir çıkış ve bir inişi belirler.
Aynı soldan sağa geçiş sırasında derlenmiş uygulamalar her prefix'in üst zarfını monoton bir yığınla korur. Yeni nokta gelirken, son üç zarf noktası sıkı bir üst dönüş oluşturmuyorsa ortadaki nokta atılır. Kalan önceki köşe kaydedilir; böylece daha sonra herhangi bir prefix'in üst zarfı geriye doğru bağlantılarla gezilebilir.
\(P(k)\) hesabında önce \(k-1\) zirvesi görünür kabul edilir. Sonra daha soldaki prefix'te, mevcut en iyi eğimden daha küçük bir eğime sahip herhangi bir nokta olup olmadığı sorulur. Bu soru sadece o prefix'in üst zarf zinciri üzerinde dolaşılarak cevaplanır. Eğer daha iyi bir zarf noktası yoksa arama biter. Varsa, uygulama solda mevcut en iyi eğimden daha küçük ilk indeksi bulana kadar geri yürür; o indeks bir sonraki görünür zirvedir ve süreç tekrarlanır.
C++ sürümü, tam hesaplamaya başlamadan önce küçük bir başlangıç aralığını doğrudan tam taramayla ve bilinen kontrol toplamlarıyla doğrular. C++ ve Java sürümleri kalan \(k\) aralığını birden çok iş parçacığına böler ve kısmi toplamları birleştirir. Python sürümü ise bu geometrik yöntemi saf Python'da yeniden yazmaz; derlenmiş optimize çözücüyü çağırır ve elde edilen sayısal sonucu döndürür.
\(M\), ilk \(2N\) asalı elde etmek için gereken elek sınırı olsun; uygulamada bu, \(N=2{,}500{,}000\) için yeterli sabit bir üst sınırdır. Elek \(O(M\log\log M)\) zaman ve seçilen gösterimde \(O(M)\) bellek kullanır. Koordinatların ve prefix üst zarf bağlantılarının kurulması \(O(N)\) zaman ve \(O(N)\) bellek ister. Tüm zirve çiftlerini doğrudan tarayan yöntem \(O(N^2)\) olurdu. Uygulanan yöntem geometrik veri için yine \(O(N)\) depolama kullanır, fakat üst zarf varlık testleriyle aramanın büyük kısmını budar; bu yüzden gerçek Project Euler örneği pratikte çözülebilir hale gelir. Kod, arama aşaması için kareselden daha iyi resmî bir en-kötü-durum bağı vermediğinden, doğru ifade "kanıtlanmış asimptotik iyileşme" değil, "çok güçlü pratik hızlanma"dır.
Se toman los primos consecutivos \(p_1,p_2,p_3,\dots\) y se agrupan en pares \((p_1,p_2),(p_3,p_4),\dots\). Partiendo de \((0,0)\), se sube con pendiente \(+1\) durante una distancia horizontal \(p_{2k-1}\), y luego se baja con pendiente \(-1\) durante una distancia horizontal \(p_{2k}\). El extremo de la subida del par \(k\) es el pico \(k\).
Para cada pico \(k\), \(P(k)\) es el número de picos anteriores visibles desde \(k\): un pico \(j\lt k\) es visible si el segmento que une \(j\) con \(k\) permanece estrictamente por encima de todos los picos intermedios. Hay que calcular
$$\sum_{k=1}^{N} P(k),\qquad N=2{,}500{,}000.$$
El método implementado convierte la visibilidad en un problema de pendientes ordenadas. Una vez hecha esa reformulación, la búsqueda se recorta con información de la envolvente convexa superior de los prefijos de la secuencia de picos.
Sea \((x_k,y_k)\) el pico \(k\). La construcción produce
$$x_k=\sum_{i=1}^{2k-1} p_i,$$
porque hasta la cima de la subida número \(k\) se han consumido exactamente esos desplazamientos horizontales. La altura viene dada por
$$y_k=\sum_{i=1}^{2k-1} (-1)^{i+1} p_i,$$
ya que los primos de índice impar elevan la cordillera y los de índice par la vuelven a bajar. En particular,
$$x_1 \lt x_2 \lt x_3 \lt \cdots,$$
de modo que toda pregunta de visibilidad se reduce a comparar pendientes hacia un extremo derecho fijo.
Fijemos un pico \(k\) y definamos
$$s_k(j)=\frac{y_k-y_j}{x_k-x_j},\qquad 1\le j\lt k.$$
Si \(j\lt i\lt k\), entonces el pico intermedio \(i\) queda estrictamente por debajo de la cuerda que une \(j\) con \(k\) exactamente cuando
$$y_i \lt y_k-\frac{y_k-y_j}{x_k-x_j}(x_k-x_i).$$
Reordenando se obtiene
$$\frac{y_k-y_i}{x_k-x_i} \gt \frac{y_k-y_j}{x_k-x_j},$$
es decir, \(s_k(i)\gt s_k(j)\). Por tanto, el pico \(j\) es visible desde \(k\) si y solo si
$$s_k(j)\lt s_k(i)\qquad\text{para todo }i\text{ con }j\lt i\lt k.$$
Al recorrer \(j=k-1,k-2,\dots,1\), los picos visibles son exactamente aquellos donde la pendiente alcanza un nuevo mínimo estricto. El vecino inmediato \(k-1\) siempre es visible, porque no hay ningún pico intermedio.
Las coordenadas crecen mucho, así que comparar divisiones en coma flotante sería innecesariamente frágil. Como todos los denominadores son positivos, se puede usar la equivalencia
$$s_k(j_1)\lt s_k(j_2)\iff (y_k-y_{j_1})(x_k-x_{j_2}) \lt (y_k-y_{j_2})(x_k-x_{j_1}).$$
Eso elimina cualquier error de redondeo. Las implementaciones compiladas evalúan estos productos cruzados con aritmética entera lo bastante ancha para mantener la comparación exacta.
Supongamos que el pico visible actual durante el barrido de \(k\) es \(b\). El siguiente pico visible, si existe, debe estar dentro del prefijo \(\{1,2,\dots,b-1\}\). Para un extremo derecho fijo \(k\), el mínimo de \(s_k(j)\) en ese prefijo se alcanza en la envolvente convexa superior, no en un punto interior por debajo de ella.
Geométricamente, si una recta que pasa por el pico \(k\) gira hacia abajo, el primer punto del prefijo que puede tocar es un vértice de la envolvente superior. Por eso
$$\exists\, j\lt b\text{ con }s_k(j)\lt s_k(b)\iff \exists\, v\text{ en la envolvente superior de }\{1,\dots,b-1\}\text{ con }s_k(v)\lt s_k(b).$$
Esto no identifica directamente el siguiente pico visible, pero sí da una prueba rápida de existencia. Si ningún vértice de la envolvente mejora la pendiente, el barrido puede detenerse inmediatamente.
Los primeros nueve picos salen de los primos \(2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61\). Sus coordenadas son
$$\begin{aligned} (x_1,y_1)&=(2,2),\\ (x_2,y_2)&=(10,4),\\ (x_3,y_3)&=(28,8),\\ (x_4,y_4)&=(58,12),\\ (x_5,y_5)&=(100,16),\\ (x_6,y_6)&=(160,18),\\ (x_7,y_7)&=(238,22),\\ (x_8,y_8)&=(328,26),\\ (x_9,y_9)&=(440,32). \end{aligned}$$
Para \(k=9\), las pendientes hacia los picos anteriores son
$$\begin{aligned} s_9(8)&=\frac{6}{112},\\ s_9(7)&=\frac{10}{202},\\ s_9(6)&=\frac{14}{280},\\ s_9(5)&=\frac{16}{340},\\ s_9(4)&=\frac{20}{382},\\ s_9(3)&=\frac{24}{412},\\ s_9(2)&=\frac{28}{430},\\ s_9(1)&=\frac{30}{438}. \end{aligned}$$
Al barrer de derecha a izquierda, los mínimos récord aparecen en \(j=8\), luego en \(j=7\) y después en \(j=5\). Por tanto,
$$P(9)=3.$$
El mismo razonamiento da \(P(3)=1\), y además
$$\sum_{k=1}^{100} P(k)=227$$
coincide con los puntos de control usados por la implementación.
Las implementaciones en C++, Python y Java usan la misma geometría. Primero generan los primeros \(2N\) primos con una criba que solo almacena impares. Después construyen las coordenadas de los picos en una sola pasada, emparejando cada par consecutivo de primos como una subida y una bajada.
Durante esa misma pasada de izquierda a derecha, las implementaciones compiladas mantienen la envolvente superior de cada prefijo mediante una pila monótona. Cuando llega un nuevo punto, se elimina el vértice anterior mientras los tres últimos puntos de la envolvente no formen un giro superior estricto. El predecesor que queda se guarda para poder recorrer más tarde, hacia atrás, la envolvente superior de cualquier prefijo usando solo memoria constante adicional por punto.
Para calcular \(P(k)\), la implementación empieza en el pico \(k-1\), que siempre es visible. Luego pregunta repetidamente si el prefijo anterior contiene algún punto con una pendiente menor que la del mejor pico visible actual. Esa pregunta se responde recorriendo únicamente la cadena almacenada de la envolvente superior del prefijo. Si la respuesta es negativa, la búsqueda termina. Si es positiva, la implementación camina hacia la izquierda hasta encontrar el primer índice cuya pendiente es menor que la mejor actual; ese índice es el siguiente pico visible, y el proceso continúa.
La versión en C++ también verifica el primer tramo pequeño contra un barrido directo completo y contra sumas de control conocidas antes de lanzar el cálculo grande. Las versiones en C++ y Java reparten el resto de los valores de \(k\) entre varios hilos de trabajo y suman los resultados parciales. La implementación en Python no reescribe esta geometría en Python puro; delega en el solucionador compilado optimizado y devuelve la respuesta numérica producida por él.
Sea \(M\) el límite de la criba necesario para obtener los primeros \(2N\) primos; en la implementación es una cota fija suficiente para \(N=2{,}500{,}000\). La criba cuesta \(O(M\log\log M)\) tiempo y \(O(M)\) memoria en la representación elegida. Construir las coordenadas y los enlaces de la envolvente de los prefijos cuesta \(O(N)\) tiempo y \(O(N)\) memoria. Un barrido directo de visibilidad sobre todos los pares de picos sería \(O(N^2)\). El método implementado conserva \(O(N)\) memoria geométrica, pero elimina gran parte del trabajo con pruebas de existencia sobre la envolvente superior, lo que vuelve tratable la instancia real del problema. El código no aporta una demostración formal de una cota peor-caso mejor que cuadrática para la fase de búsqueda; por eso la afirmación correcta es una aceleración práctica muy fuerte, no una mejora asintótica ya demostrada.
取连续素数 \(p_1,p_2,p_3,\dots\)，并按 \((p_1,p_2),(p_3,p_4),\dots\) 配对。从 \((0,0)\) 出发，先以斜率 \(+1\) 上升，水平长度为 \(p_{2k-1}\)；再以斜率 \(-1\) 下降，水平长度为 \(p_{2k}\)。第 \(k\) 对中的上升段终点就是第 \(k\) 个山峰。
对每个山峰 \(k\)，定义 \(P(k)\) 为它左侧可见山峰的个数：若 \(j\lt k\)，并且连接山峰 \(j\) 与山峰 \(k\) 的线段严格高于中间所有山峰，则称 \(j\) 从 \(k\) 可见。题目要求计算
$$\sum_{k=1}^{N} P(k),\qquad N=2{,}500{,}000.$$
实现中的核心思想，是把“可见性”改写成“斜率是否刷新当前最小值”的问题。完成这个转换后，再用每个前缀的上凸包信息，把大量不可能产生新可见峰的搜索直接剪掉。
记第 \(k\) 个山峰坐标为 \((x_k,y_k)\)。根据构造过程，横坐标满足
$$x_k=\sum_{i=1}^{2k-1} p_i,$$
因为走到第 \(k\) 次上升的顶点之前，恰好已经消耗了前 \(2k-1\) 个素数对应的水平步长。纵坐标则为
$$y_k=\sum_{i=1}^{2k-1} (-1)^{i+1} p_i,$$
因为奇数下标的素数把高度往上推，偶数下标的素数把高度往下拉。特别地，
$$x_1 \lt x_2 \lt x_3 \lt \cdots,$$
所以对固定的右端点 \(k\)，所有可见性判断都可以转化成若干个“从 \(k\) 指向左边点的斜率”之间的比较。
固定一个右端点山峰 \(k\)，定义
$$s_k(j)=\frac{y_k-y_j}{x_k-x_j},\qquad 1\le j\lt k.$$
现在取任意中间山峰 \(i\)，满足 \(j\lt i\lt k\)。点 \(i\) 严格落在连接 \(j\) 与 \(k\) 的弦下方，当且仅当
$$y_i \lt y_k-\frac{y_k-y_j}{x_k-x_j}(x_k-x_i).$$
整理可得
$$\frac{y_k-y_i}{x_k-x_i} \gt \frac{y_k-y_j}{x_k-x_j},$$
也就是 \(s_k(i)\gt s_k(j)\)。因此，山峰 \(j\) 从 \(k\) 可见，当且仅当
$$s_k(j)\lt s_k(i)\qquad\text{对所有 }j\lt i\lt k\text{ 都成立。}$$
这说明：若按 \(j=k-1,k-2,\dots,1\) 的顺序从右向左扫描，那么所有可见山峰，恰好就是那些使斜率成为“新的严格最小值”的位置。最近的山峰 \(k-1\) 总是可见，因为它与 \(k\) 之间没有中间山峰。
坐标规模很大，直接做浮点除法会带来不必要的精度风险。由于所有分母都是正数，可以把斜率比较写成
$$s_k(j_1)\lt s_k(j_2)\iff (y_k-y_{j_1})(x_k-x_{j_2}) \lt (y_k-y_{j_2})(x_k-x_{j_1}).$$
这样就完全避免了舍入误差。编译型实现用足够宽的整数算术来完成这些交叉乘法，因此即使在题目的完整规模下，比较仍然是精确的。
设当前已经找到的可见山峰是 \(b\)。那么下一个可见山峰如果存在，必定出现在前缀 \(\{1,2,\dots,b-1\}\) 中。对于固定的右端点 \(k\)，在这个前缀里使 \(s_k(j)\) 最小的点，不会是落在凸包内部或下方的点，而一定在该前缀的上凸包顶点上取得。
几何上可以这样理解：从右侧的点 \(k\) 引一条直线并向下旋转，最先接触到前缀点集的位置，一定是上凸包的一个顶点。因此有
$$\exists\, j\lt b\text{ 使 }s_k(j)\lt s_k(b)\iff \exists\, v\text{ 属于 }\{1,\dots,b-1\}\text{ 的上凸包，且 }s_k(v)\lt s_k(b).$$
这个结论并不会直接告诉我们“下一个可见山峰是谁”，但它给出了一个极快的存在性判定。如果上凸包上没有任何点能改进当前斜率，那么搜索就可以立刻停止。
前九个山峰由素数 \(2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61\) 构成。对应坐标为
$$\begin{aligned} (x_1,y_1)&=(2,2),\\ (x_2,y_2)&=(10,4),\\ (x_3,y_3)&=(28,8),\\ (x_4,y_4)&=(58,12),\\ (x_5,y_5)&=(100,16),\\ (x_6,y_6)&=(160,18),\\ (x_7,y_7)&=(238,22),\\ (x_8,y_8)&=(328,26),\\ (x_9,y_9)&=(440,32). \end{aligned}$$
对 \(k=9\) 来说，连向前面各山峰的斜率依次是
$$\begin{aligned} s_9(8)&=\frac{6}{112},\\ s_9(7)&=\frac{10}{202},\\ s_9(6)&=\frac{14}{280},\\ s_9(5)&=\frac{16}{340},\\ s_9(4)&=\frac{20}{382},\\ s_9(3)&=\frac{24}{412},\\ s_9(2)&=\frac{28}{430},\\ s_9(1)&=\frac{30}{438}. \end{aligned}$$
从右往左扫描时，严格新最小值出现在 \(j=8\)、随后是 \(j=7\)、再随后是 \(j=5\)。因此
$$P(9)=3.$$
同样的方法还可得到 \(P(3)=1\)，并且
$$\sum_{k=1}^{100} P(k)=227$$
与实现里使用的校验点完全一致。
C++、Python 和 Java 三种实现使用的是同一套几何思路。首先，程序用只存储奇数的筛法生成前 \(2N\) 个素数。然后在一次线性扫描中，把相邻两个素数解释成一次上升和一次下降，从而构造出全部山峰坐标。
在这次从左到右的扫描里，编译型实现还会同时维护“每个前缀的上凸包”。做法是使用单调栈：当新点加入时，只要最后三个凸包点没有形成严格的上侧转向，就把中间那个点弹出。保留下来的前驱关系会被记录下来，这样之后就能沿着这些前驱链接，倒着遍历任意前缀的上凸包，而每个点只需要常数额外存储。
计算 \(P(k)\) 时，程序先把 \(k-1\) 记为可见峰，因为它一定可见。之后反复判断：更左边的前缀中，是否存在某个点，其斜率比当前最佳可见峰更小。这个判定只需要沿着该前缀的上凸包链检查，而不必把整个前缀全部扫一遍。如果上凸包上都不存在更小斜率，那么搜索立即结束；如果存在，程序再从左侧往回走，找到第一个真正把斜率刷新为更小值的下标，它就是下一个可见峰，然后继续重复这个过程。
C++ 版本在正式计算前，还会用直接全扫描去核对前面一小段结果，并检查若干已知的小型校验总和。C++ 与 Java 版本都会把剩余的 \(k\) 区间分配给多个工作线程，再把部分和相加。Python 版本并没有在纯 Python 中重写这套几何算法，而是调用已经编译好的优化求解器，并把得到的数字答案解析出来。
设 \(M\) 为获得前 \(2N\) 个素数所需的筛法上界；在实现中，它是一个对 \(N=2{,}500{,}000\) 足够的固定界。筛法耗时 \(O(M\log\log M)\)，并在所选表示下使用 \(O(M)\) 内存。构造坐标与前缀上凸包前驱链接需要 \(O(N)\) 时间和 \(O(N)\) 内存。如果按定义对每个 \(k\) 都去检查全部更左侧山峰，那么总复杂度会是 \(O(N^2)\)。实际实现仍然只保留 \(O(N)\) 级别的几何存储，但通过“先检查上凸包上是否存在更优斜率”这一剪枝，大幅减少了真正需要回扫的工作量，从而让题目的实际规模变得可计算。需要诚实指出的是，代码本身并没有给出一个严格优于二次复杂度的最坏情况证明，所以这里最准确的说法是“实践中极强的加速”，而不是“已经证明的渐近复杂度改进”。
Берутся последовательные простые числа \(p_1,p_2,p_3,\dots\) и объединяются в пары \((p_1,p_2),(p_3,p_4),\dots\). Начиная из точки \((0,0)\), мы поднимаемся с наклоном \(+1\) на горизонтальное расстояние \(p_{2k-1}\), а затем спускаемся с наклоном \(-1\) на расстояние \(p_{2k}\). Конец подъёма в \(k\)-й паре и есть пик номер \(k\).
Для каждого пика \(k\) величина \(P(k)\) означает число более ранних пиков, видимых из \(k\): пик \(j\lt k\) считается видимым, если отрезок, соединяющий пики \(j\) и \(k\), проходит строго выше всех промежуточных пиков. Требуется вычислить
$$\sum_{k=1}^{N} P(k),\qquad N=2{,}500{,}000.$$
Реализованный метод сводит условие видимости к задаче о порядке наклонов. После этого поиск резко ускоряется за счёт информации о верхней выпуклой оболочке каждого префикса последовательности пиков.
Пусть \((x_k,y_k)\) обозначает координаты пика \(k\). Из конструкции сразу следует
$$x_k=\sum_{i=1}^{2k-1} p_i,$$
потому что к моменту достижения вершины \(k\)-го подъёма мы уже прошли именно эти горизонтальные шаги. Высота равна
$$y_k=\sum_{i=1}^{2k-1} (-1)^{i+1} p_i,$$
так как простые с нечётным индексом поднимают горный профиль, а с чётным индексом опускают его. В частности,
$$x_1 \lt x_2 \lt x_3 \lt \cdots,$$
поэтому любой вопрос о видимости превращается в сравнение наклонов к фиксированной правой точке.
Зафиксируем пик \(k\) и введём
$$s_k(j)=\frac{y_k-y_j}{x_k-x_j},\qquad 1\le j\lt k.$$
Если \(j\lt i\lt k\), то промежуточный пик \(i\) лежит строго ниже хорды, соединяющей \(j\) и \(k\), тогда и только тогда, когда
$$y_i \lt y_k-\frac{y_k-y_j}{x_k-x_j}(x_k-x_i).$$
После преобразования получаем
$$\frac{y_k-y_i}{x_k-x_i} \gt \frac{y_k-y_j}{x_k-x_j},$$
то есть \(s_k(i)\gt s_k(j)\). Значит, пик \(j\) видим из \(k\) тогда и только тогда, когда
$$s_k(j)\lt s_k(i)\qquad\text{для всех }i\text{, удовлетворяющих }j\lt i\lt k.$$
Следовательно, если просматривать индексы \(j=k-1,k-2,\dots,1\), то видимыми окажутся ровно те пики, на которых наклон становится новым строгим минимумом. Ближайший пик \(k-1\) всегда видим, потому что между ним и \(k\) нет промежуточной вершины.
Координаты быстро становятся большими, поэтому сравнивать вещественные частные было бы ненадёжно. Поскольку знаменатели положительны, можно использовать эквивалентность
$$s_k(j_1)\lt s_k(j_2)\iff (y_k-y_{j_1})(x_k-x_{j_2}) \lt (y_k-y_{j_2})(x_k-x_{j_1}).$$
Такое сравнение совершенно точно и не содержит ошибок округления. В компилируемых реализациях эти поперечные произведения считаются с помощью достаточно широкой целочисленной арифметики.
Пусть текущий найденный видимый пик при обработке \(k\) равен \(b\). Тогда следующий видимый пик, если он существует, должен лежать в префиксе \(\{1,2,\dots,b-1\}\). Для фиксированной правой точки \(k\) минимум \(s_k(j)\) по этому префиксу достигается на верхней выпуклой оболочке, а не во внутренней точке ниже неё.
Геометрически это означает, что если вращать вниз прямую, проходящую через пик \(k\), то первым касанием с точками префикса будет вершина верхней оболочки. Поэтому
$$\exists\, j\lt b\text{ такое, что }s_k(j)\lt s_k(b)\iff \exists\, v\text{ на верхней оболочке }\{1,\dots,b-1\}\text{ с }s_k(v)\lt s_k(b).$$
Это ещё не даёт индекс следующего видимого пика напрямую, но даёт быстрый тест существования. Если ни одна вершина оболочки не улучшает текущий наклон, поиск можно немедленно остановить.
Первые девять пиков строятся из простых чисел \(2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61\). Их координаты равны
$$\begin{aligned} (x_1,y_1)&=(2,2),\\ (x_2,y_2)&=(10,4),\\ (x_3,y_3)&=(28,8),\\ (x_4,y_4)&=(58,12),\\ (x_5,y_5)&=(100,16),\\ (x_6,y_6)&=(160,18),\\ (x_7,y_7)&=(238,22),\\ (x_8,y_8)&=(328,26),\\ (x_9,y_9)&=(440,32). \end{aligned}$$
Для \(k=9\) наклоны к предыдущим вершинам равны
$$\begin{aligned} s_9(8)&=\frac{6}{112},\\ s_9(7)&=\frac{10}{202},\\ s_9(6)&=\frac{14}{280},\\ s_9(5)&=\frac{16}{340},\\ s_9(4)&=\frac{20}{382},\\ s_9(3)&=\frac{24}{412},\\ s_9(2)&=\frac{28}{430},\\ s_9(1)&=\frac{30}{438}. \end{aligned}$$
При просмотре справа налево новые строгие минимумы появляются на \(j=8\), затем на \(j=7\), затем на \(j=5\). Следовательно,
$$P(9)=3.$$
Тем же способом получается \(P(3)=1\), а контрольная сумма
$$\sum_{k=1}^{100} P(k)=227$$
совпадает с контрольными точками, использованными в реализации.
Реализации на C++, Python и Java опираются на одну и ту же геометрическую схему. Сначала генерируются первые \(2N\) простых чисел при помощи решета, хранящего только нечётные числа. Затем координаты всех пиков строятся за один проход, в котором каждая пара соседних простых задаёт подъём и последующий спуск.
Во время этого же прохода слева направо компилируемые реализации поддерживают верхнюю оболочку каждого префикса с помощью монотонного стека. Когда добавляется новая точка, предыдущая вершина оболочки удаляется до тех пор, пока последние три точки оболочки не образуют строгий верхний поворот. Оставшаяся связь с предыдущей вершиной сохраняется, так что позже верхнюю оболочку любого префикса можно обходить назад, тратя лишь константную дополнительную память на точку.
Чтобы вычислить \(P(k)\), алгоритм начинает с пика \(k-1\), который заведомо видим. Затем он многократно проверяет, есть ли в более раннем префиксе точка с наклоном меньше, чем у текущего лучшего видимого пика. Эта проверка выполняется только по сохранённой цепочке верхней оболочки префикса. Если улучшения нет, поиск завершается. Если оно есть, алгоритм идёт влево, пока не найдёт первый индекс с меньшим наклоном; этот индекс и есть следующий видимый пик, после чего процесс повторяется.
Версия на C++ дополнительно сверяет начальный небольшой диапазон с полным прямым сканированием и с известными контрольными суммами, прежде чем запускать основной расчёт. Версии на C++ и Java делят оставшийся диапазон значений \(k\) между несколькими рабочими потоками и складывают частичные суммы. Реализация на Python не переписывает эту геометрию на чистом Python, а передаёт работу оптимизированному компилируемому решателю и возвращает полученный числовой ответ.
Пусть \(M\) — граница решета, достаточная для получения первых \(2N\) простых; в реализации это фиксированная верхняя оценка, достаточная для \(N=2{,}500{,}000\). Решето работает за \(O(M\log\log M)\) времени и использует \(O(M)\) памяти в выбранном представлении. Построение координат и ссылок на верхнюю оболочку префиксов требует \(O(N)\) времени и \(O(N)\) памяти. Полный наивный перебор всех пар пиков дал бы \(O(N^2)\). Реализованный метод по-прежнему хранит лишь \(O(N)\) геометрических данных, но резко сокращает объём поиска благодаря тестам существования улучшения на верхней оболочке, что и делает реальный экземпляр Project Euler вычислимым на практике. При этом в коде нет формального доказательства оценки лучше квадратичной в худшем случае для самой фазы поиска, поэтому корректно говорить о сильном практическом ускорении, а не о строго доказанной асимптотической границе.
نأخذ الأعداد الأولية المتتالية \(p_1,p_2,p_3,\dots\) ونقسمها إلى أزواج على الصورة \((p_1,p_2),(p_3,p_4),\dots\). انطلاقًا من النقطة \((0,0)\) نصعد بميل \(+1\) لمسافة أفقية مقدارها \(p_{2k-1}\)، ثم نهبط بميل \(-1\) لمسافة أفقية مقدارها \(p_{2k}\). نهاية الصعود في الزوج رقم \(k\) هي القمة رقم \(k\).
لكل قمة \(k\)، نرمز بـ \(P(k)\) إلى عدد القمم السابقة المرئية منها: تكون القمة \(j\lt k\) مرئية إذا كان المقطع الواصل بين القمتين \(j\) و\(k\) يقع بدقة فوق جميع القمم الواقعة بينهما. المطلوب هو حساب
$$\sum_{k=1}^{N} P(k),\qquad N=2{,}500{,}000.$$
الفكرة الأساسية في التنفيذ هي تحويل شرط الرؤية إلى مسألة ترتيب ميول. وبعد هذا التحويل يمكن تقليص البحث كثيرًا باستعمال معلومات الغلاف المحدب العلوي لكل بادئة من تسلسل القمم.
لتكن \((x_k,y_k)\) إحداثيات القمة رقم \(k\). من البناء نحصل مباشرة على
$$x_k=\sum_{i=1}^{2k-1} p_i,$$
لأننا قبل الوصول إلى قمة الصعود رقم \(k\) نكون قد استهلكنا تمامًا هذه الإزاحات الأفقية. أما الارتفاع فيساوي
$$y_k=\sum_{i=1}^{2k-1} (-1)^{i+1} p_i,$$
إذ إن الأعداد الأولية ذات الفهرس الفردي ترفع السلسلة الجبلية، بينما الأعداد الأولية ذات الفهرس الزوجي تخفضها من جديد. وعلى وجه الخصوص،
$$x_1 \lt x_2 \lt x_3 \lt \cdots,$$
وبذلك تصبح كل مسألة رؤية مجرد مقارنة لميول من نقطة يمنى ثابتة إلى نقاط تقع يسارها.
ثبّت القمة \(k\)، وعرّف
$$s_k(j)=\frac{y_k-y_j}{x_k-x_j},\qquad 1\le j\lt k.$$
إذا أخذنا قمة وسطية \(i\) بحيث \(j\lt i\lt k\)، فإن وقوع \(i\) تحت الوتر الواصل بين \(j\) و\(k\) بشكل صارم يكافئ الشرط
$$y_i \lt y_k-\frac{y_k-y_j}{x_k-x_j}(x_k-x_i).$$
وبإعادة الترتيب نحصل على
$$\frac{y_k-y_i}{x_k-x_i} \gt \frac{y_k-y_j}{x_k-x_j},$$
أي \(s_k(i)\gt s_k(j)\). إذن تكون القمة \(j\) مرئية من \(k\) إذا وفقط إذا كان ميلها أصغر من ميل كل قمة واقعة بينهما، أي
$$s_k(j)\lt s_k(i)\qquad (j\lt i\lt k).$$
وهذا يعني أن القمم المرئية، عند المسح من اليمين إلى اليسار وفق \(j=k-1,k-2,\dots,1\)، هي بالضبط المواضع التي يصبح فيها الميل أصغر ميل شوهد حتى تلك اللحظة. والقمة المجاورة \(k-1\) مرئية دائمًا، لأنه لا توجد قمة بينهما.
الإحداثيات تكبر كثيرًا، ولذلك فإن الاعتماد على القسمة العائمة غير مرغوب فيه. ولأن جميع المقامات موجبة، يمكن كتابة المقارنة على الصورة المكافئة
$$s_k(j_1)\lt s_k(j_2)\iff (y_k-y_{j_1})(x_k-x_{j_2}) \lt (y_k-y_{j_2})(x_k-x_{j_1}).$$
بهذه الطريقة نتجنب أخطاء التقريب تمامًا. وتستعمل النسخ المترجمة حسابًا صحيحًا واسعًا لهذه الضروب التبادلية حتى تبقى المقارنة دقيقة عند الحجم الكامل للمسألة.
افترض أن القمة المرئية الحالية أثناء معالجة \(k\) هي \(b\). عندئذ لا بد أن تقع القمة المرئية التالية، إن وُجدت، داخل البادئة \(\{1,2,\dots,b-1\}\). وبالنسبة إلى نقطة يمنى ثابتة \(k\)، فإن أصغر قيمة لـ \(s_k(j)\) على هذه البادئة تتحقق على رؤوس الغلاف المحدب العلوي، لا على نقطة داخلية تقع تحته.
هندسيًا، إذا أدرنا مستقيمًا يمر بالقمة \(k\) إلى الأسفل، فإن أول نقطة يلمسها من تلك البادئة تكون رأسًا من رؤوس الغلاف العلوي. إذا رمزنا إلى الغلاف العلوي للبادئة \(\{1,\dots,b-1\}\) بالرمز \(U_{b-1}\)، فإن
$$\exists\, j\lt b:\ s_k(j)\lt s_k(b)\iff \exists\, v\in U_{b-1}:\ s_k(v)\lt s_k(b).$$
هذا لا يحدد مباشرةً من هي القمة المرئية التالية، لكنه يوفر اختبار وجود سريعًا جدًا. فإذا لم يوجد على الغلاف العلوي أي رأس يحسن الميل الحالي، يمكن إنهاء البحث فورًا.
تُبنى القمم التسع الأولى من الأعداد الأولية \(2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61\). وتكون الإحداثيات
$$\begin{aligned} (x_1,y_1)&=(2,2),\\ (x_2,y_2)&=(10,4),\\ (x_3,y_3)&=(28,8),\\ (x_4,y_4)&=(58,12),\\ (x_5,y_5)&=(100,16),\\ (x_6,y_6)&=(160,18),\\ (x_7,y_7)&=(238,22),\\ (x_8,y_8)&=(328,26),\\ (x_9,y_9)&=(440,32). \end{aligned}$$
وعند \(k=9\) تكون الميول نحو القمم السابقة هي
$$\begin{aligned} s_9(8)&=\frac{6}{112},\\ s_9(7)&=\frac{10}{202},\\ s_9(6)&=\frac{14}{280},\\ s_9(5)&=\frac{16}{340},\\ s_9(4)&=\frac{20}{382},\\ s_9(3)&=\frac{24}{412},\\ s_9(2)&=\frac{28}{430},\\ s_9(1)&=\frac{30}{438}. \end{aligned}$$
وعند المسح من اليمين إلى اليسار تظهر القيم الدنيا الجديدة عند \(j=8\)، ثم عند \(j=7\)، ثم عند \(j=5\). لذا
$$P(9)=3.$$
وبالطريقة نفسها نحصل على \(P(3)=1\)، كما أن
$$\sum_{k=1}^{100} P(k)=227$$
يطابق نقاط التحقق الصغيرة المستعملة في التنفيذ.
تستند تطبيقات ++C وPython وJava إلى البنية الهندسية نفسها. في البداية تُولد أول \(2N\) عددًا أوليًا باستعمال منخل يحتفظ بالأعداد الفردية فقط. ثم تُبنى إحداثيات القمم في مرور واحد، حيث يشكل كل زوج متتالٍ من الأعداد الأولية صعودًا ثم هبوطًا.
وخلال هذا المرور نفسه من اليسار إلى اليمين، تحافظ النسخ المترجمة على الغلاف العلوي لكل بادئة باستخدام مكدس رتيب. وعند وصول نقطة جديدة تُزال القمة السابقة من الغلاف ما دامت آخر ثلاث نقاط لا تكوّن انعطافًا علويًا صارمًا. ثم يُخزَّن رابط السلف المتبقي، بحيث يمكن لاحقًا تتبع الغلاف العلوي لأي بادئة إلى الخلف بكلفة تخزين إضافية ثابتة لكل نقطة.
لحساب \(P(k)\)، تبدأ الشفرة من القمة \(k-1\) لأنها مرئية حتمًا. بعد ذلك يُطرح السؤال الآتي مرارًا: هل تحتوي البادئة الأقدم على نقطة ذات ميل أصغر من ميل أفضل قمة مرئية حاليًا؟ تتم الإجابة عن هذا السؤال من خلال المرور فقط على سلسلة الغلاف العلوي المخزنة لتلك البادئة. إذا لم يوجد تحسين، يتوقف البحث. وإذا وُجد، تتحرك الشفرة إلى اليسار حتى تصل إلى أول فهرس يجعل الميل أصغر من الميل الحالي؛ ويكون ذلك الفهرس هو القمة المرئية التالية، ثم تتكرر العملية.
تضيف نسخة ++C أيضًا فحصًا في البداية يقارن مجالًا صغيرًا بمسح مباشر كامل وببعض المجاميع المرجعية المعروفة قبل تشغيل الحساب الكبير. كما توزع نسختا ++C وJava بقية قيم \(k\) على عدة خيوط عمل ثم تجمع المجاميع الجزئية. أما تنفيذ Python فلا يعيد كتابة هذه الهندسة بلغة Python الصرفة، بل يفوضها إلى المحلل المترجم المحسن ثم يعيد الجواب العددي الناتج.
ليكن \(M\) حد المنخل اللازم للحصول على أول \(2N\) عددًا أوليًا؛ وفي التنفيذ هو حد ثابت يكفي عندما يكون \(N=2{,}500{,}000\). كلفة المنخل هي \(O(M\log\log M)\) زمنيًا و\(O(M)\) ذاكرةً في التمثيل المختار. أما بناء الإحداثيات وروابط الغلاف العلوي للبوادئ فيكلف \(O(N)\) زمنًا و\(O(N)\) ذاكرةً. ولو استُخدم الفحص المباشر لتعريف الرؤية على جميع أزواج القمم لكانت الكلفة \(O(N^2)\). الطريقة المنفذة تحافظ على تخزين هندسي من رتبة \(O(N)\)، لكنها تقلل معظم العمل عبر اختبارات الوجود على الغلاف العلوي، وهذا ما يجعل حالة Project Euler الفعلية قابلة للحساب عمليًا. ومع ذلك لا يقدم الكود برهانًا نظريًا على حد أسوأ حالة أفضل من التربيعي لمرحلة البحث نفسها، لذلك فالعبارة الدقيقة هي وجود تسريع عملي قوي جدًا، لا تحسين تقاربي مثبت بصورة عامة.