用$≤m$的素数个数表示第$n$个素数

hbghlyj

Willans' Formula
$\pi(m)$为$≤m$的素数个数. 如何证明第$n$个素数为
$$p_n=1+\sum_{m=1}^{2^n}\left\lfloor\left\lfloor n\over1+\pi(m)\right\rfloor^{1/n}\right\rfloor$$

hbghlyj

MSE
Lemma:  对于任何 $x \geqslant 0,n \in \mathbb{N}_+$, $\bigl[[x]^{\frac{1}{n}}\bigr] = [x^{\frac{1}{n}}]$.

Proof: 容易看出 $\bigl[[x]^{\frac{1}{n}}\bigr] \leqslant [x^{\frac{1}{n}}]$. 假设 $a = [x^{\frac{1}{n}}] \in \mathbb{N}$, 则$$
x = (x^{\frac{1}{n}})^n \geqslant a^n \Longrightarrow [x] \geqslant a^n \Longrightarrow [x]^{\frac{1}{n}} \geqslant a \Longrightarrow \bigl[[x]^{\frac{1}{n}}\bigr] \geqslant a = [x^{\frac{1}{n}}].
$$
因此，$\bigl[[x]^{\frac{1}{n}}\bigr] = [x^{\frac{1}{n}}]$.

---

现在回到问题。根据引理，$$
\sum_{m = 1}^{2^n} \left[ \left[ \frac{n}{1 + π(m)} \right]^{\frac{1}{n}} \right] = \sum_{m = 1}^{2^n} \left[ \left( \frac{n}{1 + π(m)} \right)^{\frac{1}{n}} \right].
$$
注意 $n < 2^n$ 对于任何 $n \geqslant 1$，因此对于任何 $1 \leqslant m \leqslant 2^n$,$$
0 < \left( \frac{n}{1 + π(m)} \right)^{\frac{1}{n}} \leqslant n^{\frac{1}{n}} < 2 \Longrightarrow \left[ \left( \frac{n}{1 + π(m)} \right)^{\frac{1}{n}} \right] = 0 \text{ or } 1.
$$
By Bertrand's postulate, $p_n \leqslant 2^n$ for all $n \geqslant 1$, thus $π(m) \leqslant n - 1$ for $1 \leqslant m \leqslant p_n - 1$ and $π(m) \geqslant n$ for $p_n \leqslant m \leqslant 2^n$, which implies\begin{align*}
\sum_{m = 1}^{2^n} \left[ \left( \frac{n}{1 + π(m)} \right)^{\frac{1}{n}} \right] &= \sum_{\substack{1 \leqslant m \leqslant 2^n\\π(m) \leqslant n - 1}} \left[ \left( \frac{n}{1 + π(m)} \right)^{\frac{1}{n}} \right] + \sum_{\substack{1 \leqslant m \leqslant 2^n\\π(m) \geqslant n}} \left[ \left( \frac{n}{1 + π(m)} \right)^{\frac{1}{n}} \right]\\
&= \sum_{\substack{1 \leqslant m \leqslant 2^n\\π(m) \leqslant n - 1}} 1 + \sum_{\substack{1 \leqslant m \leqslant 2^n\\π(m) \geqslant n}} 0 = \sum_{m = 1}^{p_n - 1} 1 + \sum_{m = p_n}^{2^n} 0 = p_n - 1.
\end{align*}
因此，$$
1 + \sum_{m = 1}^{2^n} \left[ \left[ \frac{n}{1 + π(m)} \right]^{\frac{1}{n}} \right] = 1 + \sum_{m = 1}^{2^n} \left[ \left( \frac{n}{1 + π(m)} \right)^{\frac{1}{n}} \right] = p_n.
$$

hbghlyj

MSE
$$p_n=1+\sum_{m=1}^{2^n} \left\lfloor\left(\frac{n}{1+\pi(m)} \right )^{1/n} \right\rfloor$$
But it is easy to show that $n^{1/n}<2$ for all $n$, and thus
$$\left\lfloor\left(\frac{n}{1+\pi(m)} \right )^{1/n}\right\rfloor=\begin{cases}1&\text{if }\pi(m)<n\\
0&\text{otherwise}
\end{cases}$$
Since the first $n$ primes are known to be less than $2^n$, this sum counts all $m$ with $\pi(m)<n$, which is $p_n-1$. Adding $1$ gives $p_n$.