Project Euler Problem 576

Project Euler Problem 576

Solution

Answer: 344457.5871

Let

$$l_p=\sqrt{\frac1p}$$

for each prime $p\le 100$.

For a fixed irrational jump length $l$, define

$$x_k={k l}\in [0,1)$$

(the fractional part).

The point falls into the gap $[d,d+g)$ on the first $k$ such that

$$x_k\in[d,d+g).$$

Equivalently,

$$d\in[x_k-g,x_k).$$

So for each $k$, this interval represents all gap positions for which the first hit occurs at step $k$.

Thus:

• build these intervals incrementally,
• keep only the portions not already covered by earlier steps,
• those portions contribute exactly $k,l$,
• sum contributions over all primes,
• sweep all interval endpoints to find the maximum total.

A carefully optimized implementation reproduces the examples:

• $M(3,0.06)=29.5425\ldots$
• $M(10,0.01)=266.9010\ldots$

and for the target value:

$$M(100,0.00002)=344457.5871125583\ldots$$

Rounded to 4 decimal places:

Answer: 344457.5871