Project Euler Problem 353
A moon could be described by the sphere C(r) with centre (0,0,0) and radius r.
Solution
Answer: 1.2759860331
Let the angle between two stations $P,Q\in C(r)$ be $\theta$.
Since the geodesic distance on the sphere is $d=r\theta$,
$$\text{risk}(P,Q)=\left(\frac{d}{\pi r}\right)^2 =\left(\frac{\theta}{\pi}\right)^2.$$
If $P\cdot Q = r^2\cos\theta$, then
$$\theta=\arccos!\left(\frac{P\cdot Q}{r^2}\right), \qquad w(P,Q)=\left(\frac{1}{\pi}\arccos!\left(\frac{P\cdot Q}{r^2}\right)\right)^2.$$
So for each radius $r=2^n-1$, we:
- Generate all integer lattice points
$$x^2+y^2+z^2=r^2.$$ 2. Build the complete weighted graph on these stations. 3. Run Dijkstra from the North Pole $(0,0,r)$ to the South Pole $(0,0,-r)$. 4. Sum the resulting minima $M(r)$.
For example, for $r=7$, the computation gives
$$M(7)=0.178494399755\ldots$$
which matches the value stated in the problem.
A direct implementation (with symmetry reductions and efficient point generation) yields
$$\sum_{n=1}^{15} M(2^n-1) = 1.2759860331$$
rounded to 10 digits after the decimal point.
Answer: 1.2759860331