---

Problem 756

---

Approximating a Sum

Consider a function $f(k)$ defined for all positive integers $k>0$. Let $S$ be the sum of the first $n$ values of $f$. That is,
$${\displaystyle S=f(1)+f(2)+f(3)+\cdots +f(n)=\sum _{k=1}^{n}f(k)}$$

In this problem, we employ randomness to approximate this sum. That is, we choose a random, uniformly distributed, $m$-tuple of positive integers $(X_1,X_2,X_3,\cdots ,X_m)$ such that $0=X_0<X_1<X_2<\cdots <X_m\le n$ and calculate a modified sum $S^{\ast }$ as follows.
$${\displaystyle S^{\ast }=\sum _{i=1}^{m}f(X_i)(X_i-X_{i-1})}$$

We now define the error of this approximation to be $\mathrm{\Delta }=S-S^{\ast }$.

Let $\mathbb{E}(\mathrm{\Delta }|f(k),n,m)$ be the expected value of the error given the function $f(k)$, the number of terms $n$ in the sum and the length of random sample $m$.

For example, $\mathbb{E}(\mathrm{\Delta }|k,100,50)=2525/1326\approx 1.904223$ and $\mathbb{E}(\mathrm{\Delta }|\phi (k),{10}^4,{10}^2)\approx 5842.849907$, where $\phi (k)$ is Euler’s totient function.

Find $\mathbb{E}(\mathrm{\Delta }|\phi (k),12345678,12345)$ rounded to six places after the decimal point.

---

近似求和

考虑定义在所有正整数$k>0$上的函数$f(k)$。记$S$为函数$f$在前$n$个正整数上的取值之和。也就是说，
$${\displaystyle S=f(1)+f(2)+f(3)+\cdots +f(n)=\sum _{k=1}^{n}f(k)}$$

在本题中，我们加入一些随机性来近似地求和。换言之，我们均匀地随机生成一个$m$元正整数组$(X_1,X_2,X_3,\cdots ,X_m)$，且该数组满足$0=X_0<X_1<X_2<\cdots <X_m\le n$，然后按照以下方式求出近似和$S^{\ast }$。
$${\displaystyle S^{\ast }=\sum _{i=1}^{m}f(X_i)(X_i-X_{i-1})}$$

我们定义近似误差为$\mathrm{\Delta }=S-S^{\ast }$。

给定函数$f(k)$、所需计算的项数$n$和随机数组的长度$m$，记$\mathbb{E}(\mathrm{\Delta }|f(k),n,m)$为近似误差的期望值。

例如，$\mathbb{E}(\mathrm{\Delta }|k,100,50)=2525/1326\approx 1.904223$，$\mathbb{E}(\mathrm{\Delta }|\phi (k),{10}^4,{10}^2)\approx 5842.849907$，其中$\phi (k)$为欧拉总计函数。

求$\mathbb{E}(\mathrm{\Delta }|\phi (k),12345678,12345)$，并将你的答案保留小数点后六位。

---