Project Euler Problem 756
Consider a function f(k) defined for all positive integers k0.
Solution
Answer: 607238.610661
Let
$$S=\sum_{k=1}^n f(k), \qquad S^*=\sum_{i=1}^m f(X_i)(X_i-X_{i-1}),$$
where $0=X_0<X_1<\cdots<X_m\le n$ is a uniformly random $m$-subset of ${1,\dots,n}$.
We want
$$\mathbb E(\Delta)=\mathbb E(S-S^*).$$
For a fixed $k$, the coefficient of $f(k)$ in $S^*$ equals the expected gap preceding $k$ when $k$ is selected. A standard counting argument gives
$$\mathbb E(\Delta) = \sum_{k=1}^{n-m} f(k)\frac{\binom{n-k}{m}}{\binom{n}{m}}.$$
Setting $f(k)=\varphi(k)$,
$$\mathbb E(\Delta) = \sum_{k=1}^{n-m} \varphi(k)\frac{\binom{n-k}{m}}{\binom{n}{m}}.$$
The ratio satisfies the recurrence
$$w_k=\frac{\binom{n-k}{m}}{\binom{n}{m}}, \qquad w_k=w_{k-1}\frac{n-m-k+1}{n-k+1},$$
with $w_0=1$.
Using a totient sieve and this recurrence for
$$n=12345678,\qquad m=12345,$$
the computation gives
$$\mathbb E(\Delta)\approx 607238.6106613735.$$
Rounded to six digits after the decimal point:
Answer: 607238.610661