Detailed mathematical approach

Problem Summary

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.$

Mathematical Approach

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.

Step 1: Write the Peak Coordinates Explicitly

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.

Step 2: Visibility Is Equivalent to Record-Low Slopes

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\).

Step 3: Compare Slopes with Exact Integer Arithmetic

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.

Step 4: Only the Upper Hull Can Produce a Better Slope

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.

Step 5: Worked Example

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.

How the Code Works

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.

Complexity Analysis

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.

Footnotes and References

1. Problem page: Project Euler 569
2. Prime numbers: Wikipedia - Prime number
3. Convex hull: Wikipedia - Convex hull
4. Sieve of Eratosthenes: Wikipedia - Sieve of Eratosthenes
5. Cross product and orientation tests: Wikipedia - Cross product