Bertrand 假设实际上是一个定理.

设整数 $n>3$, 则在开区间 $(n,2n-2)$ 之间至少存在一个素数 $p$.

一个弱一点但更好用的公式是: 对每个 $n>1$, 总存在(至少)一个素数 $p$, 使得介于 $n$ 和 $2n$ 之间, $n<p<2n$.

References:

http://en.wikipedia.org/wiki/Bertrand\'s_postulate

若记 $a_n(k)=1^n+2^n+3^n+\cdots+k^n$, 则熟知有

\[a_1(k)=1+2+3+\cdots+k=\frac{1}{2}k(k+1)\]

• $F_{n-1}\subset F_n$
• $|F_n|=|F_{n-1}|+\varphi(n)$
• 设 $\frac{p}{q},\frac{p'}{q'},\frac{p''}{q''}$ 是 $F_n$ 中连续的三个分数. 则有 \[ p''=\lfloor\frac{q+n}{q'}\rfloor p'-p,\quad q''=\lfloor\frac{q+n}{q'}\rfloor q'-q. \]

$n$ 阶的 Farey 序列是指下述集合

\[ \biggl\{\frac{p}{q}\mid (p,q)=1,1\leqslant p,q\leqslant n\biggr\}\cup\biggr\{\frac{0}{1}\biggr\} \]

按大小排列成的一个序列. 如

\[ F_6=\biggl\{\frac{0}{1},\frac{1}{6},\frac{1}{5},\frac{1}{4},\frac{1}{3},\frac{2}{5},\frac{1}{2},\frac{3}{5},\frac{2}{3},\frac{3}{4},\frac{4}{5},\frac{5}{6},\frac{1}{1}\biggr\}\]

\[ F_7=\biggl\{\frac{0}{1},\frac{1}{7},\frac{1}{6},\frac{1}{5},\frac{1}{4},\frac{2}{7},\frac{1}{3},\frac{2}{5},\frac{3}{7},\frac{1}{2},\frac{4}{7},\frac{3}{5},\frac{2}{3},\frac{5}{7},\frac{3}{4},\frac{4}{5},\frac{5}{6},\frac{6}{7},\frac{1}{1}\biggr\} \]

\[ F_{8}=\biggl\{\frac{0}{8},\frac{1}{8},\frac{1}{7},\frac{1}{6},\frac{1}{5},\frac{1}{4},\frac{2}{7},\frac{1}{3},\frac{3}{8},\frac{2}{5},\frac{3}{7},\frac{1}{2},\frac{4}{7},\frac{3}{5},\frac{5}{8},\frac{2}{3},\frac{5}{7},\frac{3}{4},\frac{4}{5},\frac{5}{6},\frac{6}{7},\frac{7}{8},\frac{1}{1}\biggr\} \]

\[ F_{9}=\biggl\{\frac{0}{9},\frac{1}{9},\frac{1}{8},\frac{1}{7},\frac{1}{6},\frac{1}{5},\frac{2}{9},\frac{1}{4},\frac{2}{7},\frac{1}{3},\frac{3}{8},\frac{2}{5},\frac{3}{7},\frac{4}{9},\frac{1}{2},\frac{5}{9},\frac{4}{7},\frac{3}{5},\frac{5}{8},\frac{2}{3},\frac{5}{7},\frac{3}{4},\frac{7}{9},\frac{4}{5},\frac{5}{6},\frac{6}{7},\frac{7}{8},\frac{8}{9},\frac{1}{1}\biggr\} \]

\[ F_{10}=\biggl\{\frac{0}{10},\frac{1}{10},\frac{1}{9},\frac{1}{8},\frac{1}{7},\frac{1}{6},\frac{1}{5},\frac{2}{9},\frac{1}{4},\frac{2}{7},\frac{3}{10},\frac{1}{3},\frac{3}{8},\frac{2}{5},\frac{3}{7},\frac{4}{9},\frac{1}{2},\frac{5}{9},\frac{4}{7},\frac{3}{5},\frac{5}{8},\frac{2}{3},\frac{7}{10},\frac{5}{7},\frac{3}{4},\frac{7}{9},\frac{4}{5},\frac{5}{6},\frac{6}{7},\frac{7}{8},\frac{8}{9},\frac{9}{10},\frac{1}{1}\biggr\} \]

\[ F_{11}=\biggl\{\frac{0}{11},\frac{1}{11},\frac{1}{10},\frac{1}{9},\frac{1}{8},\frac{1}{7},\frac{1}{6},\frac{2}{11},\frac{1}{5},\frac{2}{9},\frac{1}{4},\frac{3}{11},\frac{2}{7},\frac{3}{10},\frac{1}{3},\frac{4}{11},\frac{3}{8},\frac{2}{5},\frac{3}{7},\frac{4}{9},\frac{5}{11},\frac{1}{2},\frac{6}{11},\frac{5}{9},\frac{4}{7},\frac{3}{5},\frac{5}{8},\frac{7}{11},\frac{2}{3},\frac{7}{10},\frac{5}{7},\frac{8}{11},\frac{3}{4},\frac{7}{9},\frac{4}{5},\frac{9}{11},\frac{5}{6},\frac{6}{7},\frac{7}{8},\frac{8}{9},\frac{9}{10},\frac{10}{11},\frac{1}{1}\biggr\} \]

\[ n!=\prod_{\text{prime}\ p\leqslant n}p^{\sum_{r=1}^{+\infty}[\frac{n}{p^r}]} \]

于是

\[
v_p(n!)=\sum_{k\geqslant 1}\lfloor\frac{n}{p^k}\rfloor,\quad n\geqslant 1.
\]

这里 $v_p(m)$ 指正整数 $m$ 作素因子分解后, 其中素因子 $p$ 的幂次. 称之为 $p$ 进赋值.

推论: 对任意素数 $p$, 有

\[
\frac{n}{p}-1 < v_p(n!)\leqslant\frac{n}{p}+\frac{n}{p(p-1)}\quad (n\geqslant 1).
\]

References:

G. 特伦鲍姆(Gérald Tenenbaum) 著, 《解析与概率数论导引》,  陈华一  译.

Remark: 

这个公式可以应用于 $n!$ 的快速计算.

算法:

1. 将 $n$ 分解质因数.  $n=p_{1}^{i_1}p_{2}^{i_2}\cdots p_{m}^{i_m}$.

2. 对于 $p_k$, 计算 $d_r:=\lfloor\frac{n}{p_k^r}\rfloor$, 直到 $n < p_k^r$.

3. 求和 $s_k:=d_1+d_2+\cdots+d_r+\cdots$ .  注意这是一个有限和. 当 $n < p_k^r$ 时, $d_r=0$.

4. 最后得到 $n!$

\[
n!=p_1^{s_1}p_2^{s_2}\cdots p_m^{s_m}
\]

PNT(Prime Number Theorem)

\[ \lim_{x\rightarrow\infty}\frac{\pi(x)}{\frac{x}{\log x}}=1. \]

Remark: 这个定理是由勒让得(Legendre)与高斯(Gauss)作为猜测提出的. 直到1896年, 才由法国数学家哈达马(Hadamard)及得拉魏力泊桑(de la Vallée Poussin)同时互相独立地证明. 但是他们的证明中用到复变函数论的深邃理论, 远比契比雪夫（也译为切贝谢夫, 俄文是Чебышёв, [Remark 1] )不等式的证明曲折深奥. 这就推动人们去寻求素数定理的初等的或较简单的证明. 直到1949年, Selberg 及 Erdös 才分别给出了素数定理的初等证明.

素数定理有很多的初等证明, 但是其价值可能没有现代证明来得优美和深刻.

http://www.cnblogs.com/misaka01034/p/WeakPrimeThm.html

Euler (1740) 观察到

\[
\sum_{n=1}^{+\infty}n^{-\sigma}=\prod_{p}(1+p^{-\sigma}+p^{-2\sigma}+\cdots)=\prod_{p}(1-p^{-\sigma})^{-1}
\]

第二个等号是显然的. 第一个等号可以这样理解, 对于每个正整数 $n$, 根据算术基本定理(the Fundamental Theorem of Arithmetic)可表示为 $p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$, 于是

\[
n^{-\sigma}=(p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k})^{-\sigma}=p_1^{-a_1\sigma}p_2^{-a_2\sigma}\cdots p_k^{-a_k\sigma}.
\]

这是由 $(1+p_1^{-\sigma}+p_1^{-2\sigma}+\cdots)$, $(1+p_2^{-\sigma}+p_2^{-2\sigma}+\cdots)$, $\ldots$, $(1+p_k^{-\sigma}+p_k^{-2\sigma}+\cdots)$ 中的项相乘得到的. 反之, $\prod_{p}(1+p^{-\sigma}+p^{-2\sigma}+\cdots)$ 展开后, 成为一系列项的和, 除 1 之外, 每个项形如 $p_1^{-a_1\sigma}p_2^{-a_2\sigma}\cdots p_k^{-a_k\sigma}$. 因此第一个等号成立.

利用这个等式, Euler 给出了素数个数是无穷的新证明. 假设素数个数是有限的, 则

\[
\zeta(\sigma)=\sum_{n=1}^{\infty}\frac{1}{n^{\sigma}}=\prod_{p}\frac{1}{1-p^{-\sigma}}
\]

在 $\sigma\rightarrow 1^+$ 时仍是有界的, 但此时 $\sum_{n=1}^{\infty}\frac{1}{n^{\sigma}}$ 趋于无穷大.

粗略地说, $\zeta(\sigma)$ 的行为代表了素数的行为.

1790's, Gauss 和 Legendre 独立猜测下面的 PNT

\[
\pi(x)=\sum_{p\leqslant x}1\sim\frac{x}{\log x},\quad(x\rightarrow\infty)
\]

若记

\[
\Lambda(n)=\begin{cases}
\log p, & n=p^k,\\
0, & \text{其他}
\end{cases}
\]

则 PNT 等价地可以叙述为

\[
\psi(x):=\sum_{n\leqslant x}\Lambda(n)\sim x
\]

这里我们可以这样思考

\[
\psi(x)=\sum_{n\leqslant x}\Lambda(n)=\sum_{n=p^k\leqslant x}\log p=(\log x)\sum_{n=p^k\leqslant x}\frac{\log p}{\log x}=(\log x)\sum_{p\leqslant x}\frac{k\log p}{\log x}\sim(\log x)\sum_{p\leqslant x}1.
\]

Reference:

闵嗣鹤、严士健编《初等数论》（第二版），高等教育出版社.

Remark:

[1] 据张影老师介绍，Чебышёв 应该译为切比绍夫比较合适.

• http://primes.utm.edu/glossary/page.php?sort=SieveOfEratosthenes
• http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

设 $x>0$, $\pi(x)$ 指不超过 $x$ 的所有素数的个数. 若记 $p_i$ 为第 $i$ 个素数, 则 $\pi(x)=\max\{i|p_i\leq x\}$.

• $\pi(n)<2\log 2\cdot\frac{n}{\log n}$, 对每个大于1的整数 $n$.
• 当 $x\rightarrow+\infty$ 时, $\pi(x)\sim\frac{x}{\log x}$.
• 存在常数 $A,B > 0$, 使得对每个大于1的整数 $n$, 有
  \[ An\log n < p_n < B n\log n. \]

黎曼假设(Riemann Hypothesis)等价于

\[
\pi(x)=\text{Li}(x)+O(\sqrt{x}\ln x)
\]

其中

\[
\mathrm{Li}(x):=\int_{2}^{x}\frac{1}{\ln t}dt=\text{li}(x)-\text{li}(2).
\]

\[
\mathrm{Li}(x)\sim\frac{x}{\ln x}\sum_{k=0}^{\infty}\frac{k!}{(\ln x)^k}=\frac{x}{\ln x}+\frac{x}{(\ln x)^2}+\frac{2!\cdot x}{(\ln x)^3}+\frac{3!\cdot x}{(\ln x)^4}+\frac{4!\cdot x}{(\ln x)^5}+\cdots
\]

$\pi(x)$ 与 $\mathrm{Li}(x)$ 之间差值的估计也可以表述为

\[
\pi(x)=\sum_{p\leqslant x}1=\int_{2}^{x}\frac{1}{\ln t}dt+O(xe^{-c\sqrt{\ln x}})
\]