---

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^*$ as follows.
$$\displaystyle S^* = \sum_{i=1}^m f(X_i)(X_i-X_{i-1})$$

We now define the error of this approximation to be $\Delta=S-S^*$.

Let $\mathbb{E}(\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}(\Delta|k,100,50) = 2525/1326 \approx 1.904223$ and $\mathbb{E}(\Delta|\varphi(k),10^4,10^2)\approx 5842.849907$, where $\varphi(k)$ is Euler’s totient function.

Find $\mathbb{E}(\Delta|\varphi(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^*$。
$$\displaystyle S^* = \sum_{i=1}^m f(X_i)(X_i-X_{i-1})$$

我们定义近似误差为$\Delta=S-S^*$。

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

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

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

---