Detailed mathematical approach

Problem Summary

Choose \(X\) uniformly from the interval \([0,1]\), and for each positive integer \(N\) define

$f_N(x)=\min_{1\le m\le N}\{mx\},\qquad F(N)=\int_0^1 f_N(x)\,dx,$

where \(\{y\}=y-\lfloor y\rfloor\) is the fractional part. The problem asks for the expected smallest fractional part among the first \(N\) multiples of a random \(x\), with the target case \(N=10000\).

A brute-force viewpoint would be hopelessly inefficient: for each \(x\) one would have to compare \(N\) different fractional parts, and doing that over a dense mesh still would not give an exact answer. The implementations avoid sampling entirely and instead partition \([0,1]\) into Farey intervals on which \(f_N(x)\) becomes a simple linear function.

Mathematical Approach

The key observation is that \(\{mx\}=mx-\lfloor mx\rfloor\) measures how far \(mx\) lies above the nearest smaller integer. So minimizing \(\{mx\}\) over \(1\le m\le N\) is equivalent to finding the best rational approximation to \(x\) from below with denominator at most \(N\).

From an expectation to an integral

Because \(X\) is uniform on \([0,1]\), the expected value in the title is exactly the integral of \(f_N(x)\). There is no probability machinery beyond that: once we know the graph of \(f_N\), the answer is its area under the curve.

For a fixed denominator \(m\), the quantity \(\{mx\}\) can be written as

$\{mx\}=mx-p \qquad\text{with}\qquad p=\lfloor mx\rfloor,$

so every candidate minimum is attached to a rational number \(p/m\le x\). This turns the original question into a geometric one about rationals of bounded denominator.

Why consecutive Farey fractions control the minimum

Let

$\frac{a}{b} \lt \frac{c}{d}$

be consecutive terms of the Farey sequence of order \(N\), denoted \(\mathcal{F}_N\). If \(x\) lies in the interval

$\frac{a}{b}\le x\le \frac{c}{d},$

then there is no reduced fraction with denominator at most \(N\) strictly between those endpoints. In particular, the best rational from below with denominator at most \(N\) stays fixed throughout the whole interval and is exactly \(a/b\).

That means the minimum fractional part is attained by the denominator \(b\):

$f_N(x)=bx-a \qquad \text{for } x\in\left[\frac{a}{b},\frac{c}{d}\right].$

At the left endpoint this value is \(0\), and as \(x\) moves rightward it rises linearly until the next Farey boundary is reached. The graph of \(f_N\) is therefore a chain of line segments, one segment for each adjacent Farey pair.

Exact contribution of one Farey interval

Adjacent Farey fractions satisfy the unimodular relation

$bc-ad=1.$

Consequently, the interval width is

$\frac{c}{d}-\frac{a}{b}=\frac{1}{bd},$

and the value of the linear segment at the right endpoint is

$f_N\!\left(\frac{c}{d}\right)=b\frac{c}{d}-a=\frac{bc-ad}{d}=\frac{1}{d}.$

So each Farey interval contributes the area of a triangle with base \(1/(bd)\) and height \(1/d\):

$\int_{a/b}^{c/d}(bx-a)\,dx=\frac{1}{2}\cdot\frac{1}{bd}\cdot\frac{1}{d}=\frac{1}{2bd^2}.$

This is the exact closed form accumulated by the implementations.

The global summation formula

Summing over all consecutive pairs in \(\mathcal{F}_N\) gives

$\boxed{F(N)=\sum_{\substack{a/b \lt c/d\\ \text{consecutive in }\mathcal{F}_N}} \frac{1}{2bd^2}.}$

Nothing is approximated in the mathematics: the only numerical issue is how to add many small positive terms stably when \(N\) is large.

Worked Example: \(N=4\)

The Farey sequence of order \(4\) is

$0,\ \frac14,\ \frac13,\ \frac12,\ \frac23,\ \frac34,\ 1.$

Therefore \(f_4(x)\) is piecewise linear:

$ f_4(x)= \begin{cases} x, & 0\le x\le \frac14,\\ 4x-1, & \frac14\le x\le \frac13,\\ 3x-1, & \frac13\le x\le \frac12,\\ 2x-1, & \frac12\le x\le \frac23,\\ 3x-2, & \frac23\le x\le \frac34,\\ 4x-3, & \frac34\le x\le 1. \end{cases} $

The interval contributions are

$\frac{1}{32},\ \frac{1}{72},\ \frac{1}{24},\ \frac{1}{36},\ \frac{1}{96},\ \frac{1}{8},$

and they add up to

$F(4)=\frac14.$

This matches the checkpoint used by the implementations and shows exactly how the Farey partition turns the expectation into a finite sum of triangle areas.

How the Code Works

The C++, Python, and Java implementations all follow the same mathematical plan: enumerate the consecutive Farey fractions of order \(N\), convert each interval into the exact term \(1/(2bd^2)\), and accumulate those terms carefully.

Enumerating adjacent Farey fractions

The sweep starts from the first two neighbors, \(0/1\) and \(1/N\). If the current neighboring pair is \(a/b \lt c/d\), the next Farey term is generated by the standard recurrence

$k=\left\lfloor\frac{N+b}{d}\right\rfloor,\qquad \frac{e}{f}=\frac{kc-a}{kd-b}.$

After processing the interval \([a/b,c/d]\), the pair advances to \(c/d \lt e/f\). Repeating this step walks through the entire Farey sequence in increasing order without building a table of all fractions in advance.

Accumulating the exact interval areas

For each current interval, the implementation adds

$\frac{1}{2bd^2}$

to the running total. Since the terms become very small near the end of the sweep, all three versions use compensated summation to reduce the loss of low-order digits. The C++ version keeps the running total in extended precision, while the Python and Java versions use standard floating-point arithmetic with the same compensation idea.

Once the right endpoint reaches \(1/1\), the next Farey update jumps past the unit interval and the traversal stops. The final decimal output is just the numerical form of the exact Farey sum above.

Complexity Analysis

Each neighboring Farey interval is visited exactly once, and each visit performs only constant-time arithmetic. The total running time is therefore linear in the number of intervals in the Farey sequence of order \(N\), which is \(\Theta(N^2)\).

The memory usage is \(O(1)\): the implementation stores only the current neighboring fractions, the running sum, and the compensation term. No large arrays, sieves, or dynamic programming tables are needed.

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=965
2. Farey sequence: Wikipedia - Farey sequence
3. Fractional part: Wikipedia - Fractional part
4. Diophantine approximation: Wikipedia - Diophantine approximation
5. Kahan summation algorithm: Wikipedia - Kahan summation algorithm