756. Approximating a Sum

Consider a function $f(k)$$f(k)$ defined for all positive integers $k>0$$k>0$. Let $S$$S$ be the sum of the first $n$$n$ values of $f$$f$. That is,

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

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

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

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

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

756. 近似和式

考虑一个定义在全体正整数上的函数 $f(k)$$f(k)$，记 $S$$S$ 为 $f$$f$ 在前 $n$$n$ 个正整数上的取值之和，也就是：

本题中，我们引入随机性以估计此和式。也就是说，我们均匀随机地选出一个满足 $0=X_0<X_1<X_2<\cdots <X_m\le n$$0=X_0 \lt X_1 \lt X_2 \lt \cdots \lt X_m \leq n$ 的 $m$$m$ 元正整数组 $(X_1,X_2,X_3,\cdots ,X_m)$$(X_1,X_2,X_3,\cdots,X_m)$ 并按下述方式计算近似和 $S^{\ast }$$S^*$：

我们定义这种近似方式的误差为 $\mathrm{\Delta }=S-S^{\ast }$$\Delta=S-S^*$。

记 $\mathbb{E}(\mathrm{\Delta }|f(k),n,m)$$\mathbb{E}(\Delta|f(k),n,m)$ 为：给定函数 $f(k)$$f(k)$，求和上标 $n$$n$ 和随机样本的长度 $m$$m$ 时，该近似方法误差的期望。

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

求 $\mathbb{E}(\mathrm{\Delta }|\phi (k),12345678,12345)$$\mathbb{E}(\Delta|\varphi(k),12345678,12345)$ 四舍五入至小数点后第六位的结果。

点 这个链接 回到源站。

点 这个链接 回到详细版题目目录。