Detailed mathematical approach

Problem Summary

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.

Mathematical Approach

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.

Step 1: View One Prime as an Irrational Rotation

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.

Step 2: Convert the Hit Condition into an Interval of Gap Starts

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.

Step 3: Paint Only the First Time Each Start Point Is Hit

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

Step 4: Turn One Prime into a Piecewise-Constant Weighted Function

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.

Step 5: Sum All Prime Contributions with an Event Sweep

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.

Worked Example: Painting Segments for \(\alpha=\sqrt{1/2}\) and \(g=0.2\)

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.

How the Code Works

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.

Complexity Analysis

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.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=576
2. Irrational rotation: Wikipedia - Irrational rotation
3. Equidistribution theorem: Wikipedia - Equidistribution theorem
4. Fractional part: Wikipedia - Fractional part
5. Sweep line algorithm: Wikipedia - Sweep line algorithm