Project Euler Problem 975

Solution

Answer: 88597366.47748

Project Euler Problem 975 is “A Winding Path” on Project Euler.

The problem defines

$$H_{a,b}(x)=\frac12-\frac1{2(a+b)}\left(b\cos(a\pi x)+a\cos(b\pi x)\right),$$

and studies the intersection curve

$$z=H_{a,b}(x)=H_{c,d}(y)$$

inside the unit cube. The required quantity is

$$G(500,1000) = \sum_{500\le p<q\le1000\atop p,q\text{ primes}} F(p,q,p,2q-p).$$

A key observation is that the topology of the path changes only at critical points of the functions $H_{a,b}$. Differentiating gives

$$H'_{a,b}(x) = \frac{ab\pi}{2(a+b)} \left(\sin(a\pi x)+\sin(b\pi x)\right).$$

Using

$$\sin u+\sin v = 2\sin\frac{u+v}{2}\cos\frac{u-v}{2},$$

the critical points occur at

$$x=\frac{2k}{a+b} \quad\text{or}\quad x=\frac{2k+1}{|a-b|}.$$

These critical values partition the square into cells where both functions are monotone. The intersection curve crosses each cell in a simple segment, so the entire path can be traced combinatorially by following cell-edge crossings and summing the absolute height changes.

I verified the implementation against the values given in the statement:

$F(3,5,3,7)\approx 7.01772$
$F(7,17,9,19)\approx 26.79578$
$G(3,20)\approx 463.80866$

all matching to the required precision.

The computed value is:

$$G(500,1000)\approx 88597366.47748.$$

Answer: 88597366.47748