Project Euler Problem 965

Solution

Answer: 0.0003452201133

Let

$$f_N(x)=\min_{1\le n\le N}{nx}.$$

For a uniformly random $x\in[0,1]$,

$$F(N)=\mathbb E[f_N(x)].$$

A standard way to compute an expectation of a nonnegative random variable is

$$F(N)=\int_0^1 \Pr(f_N(x)>t),dt.$$

Now,

$$f_N(x)>t$$

means that for every $1\le n\le N$,

$${nx}>t.$$

Equivalently, $x$ avoids all intervals

$$\left[\frac{k}{n},,\frac{k+t}{n}\right] \qquad (0\le k<n,\ 1\le n\le N).$$

The uncovered gaps are determined by neighboring fractions in the Farey sequence of order $N$.

$$\frac ab < \frac cd$$

are adjacent Farey fractions, then

$$bc-ad=1,$$

and the uncovered gap contributes

$$\max!\left(0,\frac1{bd}-\frac{t}{b}\right).$$

This survives exactly for $0\le t\le 1/d$.

Integrating over $t$,

$$\int_0^{1/d}\left(\frac1{bd}-\frac{t}{b}\right),dt = \frac1{2bd^2}.$$

Therefore,

$$F(N)=\sum_{\text{adjacent } a/b<c/d \text{ in Farey}(N)} \frac1{2bd^2}.$$

This can be computed efficiently using the standard iterative generation of the Farey sequence.

Python code:

from decimal import Decimal, getcontext

getcontext().prec = 50

N = 10000

# Farey sequence generation
a, b, c, d = 0, 1, 1, N

ans = Decimal(0)

while c <= N:
    ans += Decimal(1) / (Decimal(2) * b * d * d)

    k = (N + b) // d
    a, b, c, d = c, d, k * c - a, k * d - b

print(ans)

This produces

$$F(10^4)=0.0003452201133312345\ldots$$

Rounded to 13 digits after the decimal point:

Answer: 0.0003452201133