具体数学-第10课(素数和阶乘的有趣性质)

欧几里得数


首先我们来证明一下,素数有无穷多个。

假设素数只有$k$个,分别为$2,3, \ldots ,{P_k}$,那么我们构造下面的数字:
\[M = 2 \cdot 3 \cdot \ldots \cdot {P_k} + 1\]
显然$M$无法被$2,3, \ldots ,{P_k}$中的任意一个整除,那么要么$M$可以被其他的素数整除,要么$M$自己就是一个素数。所以素数有无穷多个。

下面我们来定义欧几里得数,是用递归形式来定义的:
\[{e_n} = {e_0}{e_1}{e_2} \ldots {e_{n - 1}} + 1\]

那么欧几里得数是否是素数呢?当然不是的,${e_5} = 1807 = 13 \cdot 139$。

但是欧几里得数还是有很多奇妙的性质。

性质1
\[\gcd ({e_m},{e_n}) = 1,m \ne n\]
证明:
假设$n > m$,那么有
\[\gcd ({e_m},{e_n}) = \gcd ({e_m},{e_0}{e_1} \ldots {e_m}{e_{m + 1}} \ldots {e_{n - 1}} + 1) = \gcd (1,{e_m}) = 1\]
性质2
如果令$q_j$等于$e_j$的最小素因子,那么${q_1},{q_2}, \ldots $就是一个不重复的素数序列,这也证明了素数有无穷多个。
性质3
\[{e_n} = {e_0}{e_1}{e_2} \ldots {e_{n - 1}} + 1 = ({e_{n - 1}} - 1){e_{n - 1}} + 1 = e_{n - 1}^2 - {e_{n - 1}} + 1\]
在后面的章节可以证明:
\[{e_n} = \left\lfloor { {E^{ {2^n}}} + \frac{1}{2}} \right\rfloor \]
其中$E \approx 1.264$

下面我们稍稍探究一下下面这个数的性质:
\[{2^p} - 1\]
这个数如果是素数,那么就被叫做梅森素数,那么它在什么情况下是素数呢?

首先$p$不能是合数,因为有
\[{2^{km}} - 1 = ({2^m} - 1)({2^{m(k - 1)}} + {2^{m(k - 2)}} + \cdots + 1)\]
但是如果$p$是素数,这个数也不一定是素数,2017年年末美国一个电气工程师发现了人类历史上最大的梅森素数——${2^{77232917}} - 1$。

阶乘

阶乘定义如下:
\[n! = 1 \cdot 2 \cdot \ldots \cdot n = \prod\limits_{k = 1}^n k \]
所以有
\[n{!^2} = (1 \cdot 2 \cdot \ldots \cdot n)(n \cdot \ldots \cdot 2 \cdot 1) = \prod\limits_{k = 1}^n {k(n + 1 - k)} \]
由基本不等式可以得到
\[n \le k(n + 1 - k) \le \frac{ { { {(n + 1)}^2}}}{4}\]
所以
\[\prod\limits_{k = 1}^n n \le n{!^2} \le \prod\limits_{k = 1}^n {\frac{ { { {(n + 1)}^2}}}{4}} \]
所以
\[{n^{n/2}} \le n! \le \frac{ { { {(n + 1)}^n}}}{ { {2^n}}}\]
这里得到了阶乘的一个粗略范围,在后面章节中,我们会得到阶乘的一个更精确的表达式:
\[n! \sim \sqrt {2\pi n} {\left( {\frac{n}{e}} \right)^n}\]
这就是斯特林数,搞ACM还是很有用的。

下面我们来探讨$n!$中含有多少个素因子$p$,个数记为${\varepsilon _p}(n!)$。

从特殊情况讨论起,当$p = 2$的时候,我们首先看$n!$含有多少个2,然后看有多少个4,再看有多少个8,依次下去,所以答案为:
\[{\varepsilon _2}(n!) = \sum\limits_{k \ge 1} {\left\lfloor {\frac{n}{ { {2^k}}}} \right\rfloor } \]
可以看出,这个答案不就是$n$的二进制表示不停右移1位,然后相加吗?所以又可以写成:
\[{\varepsilon _2}(n!) = n - {\nu _2}(n)\]
其中${\nu _2}(n)$表示$n$的二进制表示中1的个数。

推广到一般情况:
\[{\varepsilon _p}(n!) = \sum\limits_{k \ge 1} {\left\lfloor {\frac{n}{ { {p^k}}}} \right\rfloor } \]
放缩一下有:
\[{\varepsilon _p}(n!) = \sum\limits_{k \ge 1} {\left\lfloor {\frac{n}{ { {p^k}}}} \right\rfloor } < \sum\limits_{k \ge 1} {\frac{n}{ { {p^k}}} = \frac{n}{ {p - 1}}} \]

如果我们令$p = 2$和$p = 3$可以发现:
\[{\varepsilon _2}(n!) \approx 2{\varepsilon _3}(n!)\]
但是这个式子在什么情况下相等呢?这仍然是一个未解之谜。

所以$p$对$n!$的贡献度满足如下式子:
\[{p^{ {\varepsilon _p}(n!)}} < {p^{\frac{n}{ {p - 1}}}}\]
又因为$p \le 2^{p - 1}$,所以
\[{p^{ {\varepsilon _p}(n!)}} < {p^{\frac{n}{ {p - 1}}}} \le {2^n}\]
假设素数只有$k$个,分别为$2,3, \ldots ,{P_k}$,那么有
\[n! < {({2^n})^k}\]
如果我们令$n = {2^{2k}}$,那么
\[n! < {({2^n})^k} = {2^{k{2^{2k}}}} = {2^{2k{2^{2k}}/2}} = {n^{n/2}}\]
这与我们之前推过的不等式矛盾!所以一定有无穷个素数。

设小于等于$n$的素数个数为$\pi (n)$,所以
\[n! < {2^{n\pi (n)}}\]
根据斯特林数公式,我们可以得到
\[\pi (n) > \lg (n/e)\]

互素


定义
$m$和$n$互素定义为$gcd(m, n) = 1$,记作$m \bot n$。

互素也有很多性质。

性质1
\[m/\gcd (m,n) \bot n/\gcd (m,n)\]
性质2
\[m \bot n \Leftrightarrow \min ({m_p},{n_p}) = 0\]
其中${m_p},{n_p}$就是两个数的素数指数表示法,详细定义见上一节课。
或者可以表示为
\[m \bot n \Leftrightarrow {m_p}{n_p} = 0\]
性质3
\[k \bot m,k \bot n \Leftrightarrow k \bot mn\]

Stern-Brocot树



如上图所示,Stern-Brocot树就是0到1之间的分数生成的一棵二叉树。

初始时只有$\frac{0}{1},\frac{1}{0}$两个数,第一轮将两者分母相加,分子也相加作为新的分数的分母分子。第二轮再对相邻的两个分数做相同的操作,生成新的分数序列。不断生成下去,得到了上图的二叉树。

Stern-Brocot树有下面四个性质:

  1. 0到1之间的所有有理数都出现在了这棵树中。
  2. 每个分数仅出现了1次。
  3. 每个分数都是不可约分的,即分子分母互素。
  4. 生成的序列是单调递增的。

下面我们来一个一个证明。

引理
对于相邻的两个分数$\frac{m}{n},\frac{ {m’}}{ {n’}}$,满足:
\[m’n - mn’ = 1\]
证明
用数学归纳法证明。

性质4就是证明:
\[\frac{m}{n} < \frac{ {m + m’}}{ {n + n’}} < \frac{ {m’}}{ {n’}}\]
结论是很显然的,这样性质2同时就成立了。

性质1的话,对于任意有理数$\frac{a}{b}$,假设$\frac{m}{n} < \frac{a}{b} < \frac{ {m’}}{ {n’}}$。
我们采用如下策略生成$\frac{a}{b}$。

  • 如果$\frac{ {m + m’}}{ {n + n’}} = \frac{a}{b}$,那么成功。
  • 如果$\frac{ {m + m’}}{ {n + n’}} < \frac{a}{b}$,那么令$m = m + m’,n = n + n’$。
  • 如果$\frac{ {m + m’}}{ {n + n’}} > \frac{a}{b}$,那么令$m’ = m + m’,n’ = n + n’$。

那么有
\[an - bm \ge 1,bm’ - an’ \ge 1\]
所以
\[(m’ + n’)(an - bm) + (m + n)(bm’ - an’) \ge m’ + n’ + m + n\]
而左边式子就等于$a + b$,所以
\[a + b \ge m’ + n’ + m + n\]
因为$m,n,m’,n’$都在不断增加,所以最多$a + b$轮就能生成$\frac{a}{b}$。

性质3的话,同样用数学归纳法。通过引理可以得到
\[(m + m’)n - m(n + n’) = 1\]
由扩展欧几里得定理可以得到$m + m’$与$n + n’$互素。

Farey序列
我们引申出Farey序列的概念,定义如下:
\[{F_n} = \{ a/b|\gcd (a,b) = 1,0 \le a,b \le n,0 \le a/b \le 1\} \]
关于它的更多性质,留到下一节课继续。


   转载规则


《具体数学-第10课(素数和阶乘的有趣性质)》 韦阳 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
具体数学-第11课(Stern-Brocot树和同余关系) 具体数学-第11课(Stern-Brocot树和同余关系)
Stern-Brocot树 我们接着上节课讲到的Stern-Brocot树继续往下讲。 LR序列表示对于任意分数$\frac{a}{b}$,我们从$\frac{1}{1}$开始走到它所在的结点。如果向左走就记为L,向右走记为R,最终可以
2018-05-07
下一篇 
K-best Iterative Viterbi Parsing K-best Iterative Viterbi Parsing
本文链接:EACL17 介绍 CKY算法或维特比inside算法是成分句法分析的主要方法之一,但是当产生式数量特别大之后,时间复杂度也线性增大。可行的一种方法是剪枝,但是剪枝会造成准确率的下降。所以本文就提出了一种迭代的维特比句法分析算
2018-04-24
  目录