论阶乘——从质因数分解到全体自然数求和

· · 算法·理论

本文与 这篇文章 的区别在于介绍了 \operatorname{Gamma} 以外的关于阶乘的知识。初一蒟蒻，文章可能出现问题，欢迎指出，大佬勿喷。

基本定义

阶乘，即顺序相乘，对于一个正整数 n，定义阶乘 n! 为：

n!=\prod_{i=1}^{n} i

也可以通过上面的定义发现 n!=(n-1)! \times n，因此在求阶乘时，可以递归求解。

质因数

从其他角度分析阶乘

阶乘的增长速度飞快，20! 就已经超出了 64 位整数的范围，但多数情况只需知道它的质因数分解结构。

我们把一个自然数看作由质数指数构成的向量：

n \Longleftrightarrow (v_2(n),v_3(n),v_5(n),v_7(n),\cdots)

其中 v_p(n) 表示质数 p 在 n 中的指数，这样就把乘法转换成了向量的逐分量加法，阶乘即为 1 到 x 的向量之和。

\operatorname{Legendre} 公式

定理：对于任意质数 p 和正整数 n，

v_p(n!)=\sum^{\infty}_{k=1} \left \lfloor \frac{n}{p^k} \right \rfloor

由于 p^k>n 时，\left \lfloor \frac{n}{p^k} \right \rfloor=0，无穷只需要算到 p^k \le n 为止。

::::info[证明] 能被 p 整除的数有 \left \lfloor \frac{n}{p} \right \rfloor 个，各贡献至少一个 p；

能被 p^2 整除的有 \left \lfloor \frac{n}{p^2} \right \rfloor 个，除去上一次，各自再贡献一个 p；

能被 p^3 整除的有 \left \lfloor \frac{n}{p^3} \right \rfloor 个，除去前两次，各自再贡献一个 p；

以此类推，把所有加和，就得到了总指数。 ::::

实现

long long get(long long n,long long p){
    long long ans=0;
    while(n){
        n /= p;
        ans += n;
    }
    return ans;
}

求 n! 末尾 0 的数量

由于 $v_2(n!)\ge v_5(n!)$ 恒等式成立，所以只需计算： $$ \sum^{\infty}_{k=1} \left \lfloor \frac{n}{5^k} \right \rfloor $$ 这种方法可以快速算出一个数的阶乘末尾 $0$ 的数量。 ## $\operatorname{Kummer}$ 定理 要判断一个组合数能否被某个数整除，或者要得到它的质因数分解形式，我们需要计算： $$ v_p\binom{n}{m}=\sum^{}_{k\ge1} \left( \left \lfloor \frac{n}{p^k} \right \rfloor - \left \lfloor \frac{m}{p^k} \right \rfloor - \left \lfloor \frac{n-m}{p^k} \right \rfloor \right) $$ ### 定理 组合数 $\binom{n}{m}$ 中质数 $p$ 的指数，等于在 $p$ 进制下计算 $m+(n-m)$ 时发生的进位总次数。 $$ u_p\binom{n}{m}=\text{carry}_p(m+(n-m)) $$ ::::info[证明] 从 $\operatorname{Legendre}$ 公式出发： $$v_p\binom{n}{m} = \sum_{k \ge 1} \left(\left\lfloor \frac{n}{p^k} \right\rfloor - \left\lfloor \frac{m}{p^k} \right\rfloor - \left\lfloor \frac{n-m}{p^k} \right\rfloor \right)$$ 设 $m$、$n-m$ 和 $n$ 的 $p$ 进制展开分别为： $$m = a_0 + a_1 p + a_2 p^2 + \cdots + a_r p^r$$ $$n-m = b_0 + b_1 p + b_2 p^2 + \cdots + b_r p^r$$ $$n = c_0 + c_1 p + c_2 p^2 + \cdots + c_r p^r$$ 其中 $a_i, b_i, c_i \in \{0, 1, \dots, p-1\}$。由于 $n = m + (n-m)$，在 $p$ 进制下做加法时，第 $k$ 位会产生进位。设 $\text{carry}_k$ 表示第 $k$ 位向第 $k+1$ 位的进位值，并规定 $\text{carry}_0 = 0$。 在第 $k$ 位，有如下的**位进位方程**： $$a_k + b_k + \text{carry}_{k} = c_k + p \cdot \text{carry}_{k+1}$$ 其中 $\text{carry}_{k+1} \in \{0, 1\}$。 证明等式： $$\left\lfloor \frac{n}{p^k} \right\rfloor - \left\lfloor \frac{m}{p^k} \right\rfloor - \left\lfloor \frac{n-m}{p^k} \right\rfloor = \text{carry}_k$$ $$\left\lfloor \frac{n}{p^k} \right\rfloor = c_k + c_{k+1}p + c_{k+2}p^2 + \cdots$$ $$\left\lfloor \frac{m}{p^k} \right\rfloor = a_k + a_{k+1}p + a_{k+2}p^2 + \cdots$$ $$\left\lfloor \frac{n-m}{p^k} \right\rfloor = b_k + b_{k+1}p + b_{k+2}p^2 + \cdots$$ 因此： $$\left\lfloor \frac{n}{p^k} \right\rfloor - \left\lfloor \frac{m}{p^k} \right\rfloor - \left\lfloor \frac{n-m}{p^k} \right\rfloor$$ $$= \sum_{j=k}^{r} (c_j - a_j - b_j) p^{j-k}$$ 利用位进位方程 $a_j + b_j + \text{carry}_j = c_j + p \cdot \text{carry}_{j+1}$，可得 $c_j - a_j - b_j = \text{carry}_j - p \cdot \text{carry}_{j+1}$。 代入上式： $$\sum_{j=k}^{r} (\text{carry}_j - p \cdot \text{carry}_{j+1}) p^{j-k}$$ $$= \sum_{j=k}^{r} \text{carry}_j p^{j-k} - \sum_{j=k}^{r} \text{carry}_{j+1} p^{j-k+1}$$ 令 $t = j+1$，第二项变为： $$\sum_{t=k+1}^{r+1} \text{carry}_t p^{t-k}$$ 两项相减，中间项抵消，只剩： $$= \text{carry}_k - \text{carry}_{r+1} p^{r+1-k}$$ 最高位之上不再产生进位，$\text{carry}_{r+1} = 0$。因此： $$\left\lfloor \frac{n}{p^k} \right\rfloor - \left\lfloor \frac{m}{p^k} \right\rfloor - \left\lfloor \frac{n-m}{p^k} \right\rfloor = \text{carry}_k$$ 等式得证。 --- 将结果代回 $\operatorname{Legendre}$ 公式中： $$v_p\binom{n}{m} = \sum_{k \ge 1} \left( \left\lfloor \frac{n}{p^k} \right\rfloor - \left\lfloor \frac{m}{p^k} \right\rfloor - \left\lfloor \frac{n-m}{p^k} \right\rfloor \right) = \sum_{k \ge 1} \text{carry}_k$$ 右边的求和是 $m$ 与 $n-m$ 在 $p$ 进制下相加时发生的进位总次数。 $$v_p\binom{n}{m} = \text{carry}_p(m + (n-m))$$ 定理得证。 :::: $\operatorname{Kummer}$ 定理价值在于将组合数的整除性问题转化成进制位问题，更好地解决问题。 ## 级数估算 别的文章提到过 $\operatorname{Stirling}$ 公式，在本文仅给出定理。 ### 定理 当 $n$ 趋向于无穷大时， $$ n!\sim \sqrt{2\pi n}\left(\frac{n}{e}\right)^n $$ 更精确的， $$ \ln(n!)=n \ln n-n+\frac{1}{2}\ln(2\pi n)+\frac{1}{12n}-\frac{1}{360n^3}+\frac{1}{1260n^5}-\cdots $$ 这个级数虽然有无穷多项，但实际上并不收敛。它是一个渐近展开，在项数约 $\pi n$ 时达到最佳精度，之后继续加项反而会导致发散。 ## 全体自然数求和 有一个等式： $$ 1+2+3+4+\cdots=-\frac{1}{12} $$ 这不是普通级数求和的结果。在通常意义下，这个级数是发散的，其部分和趋向于 $+\infty$。 这个 $-\frac{1}{12}$ 实际上是黎曼 $\zeta$ 函数在 $s=-1$ 处的解析延拓值： $$\zeta(-1)=-\frac{1}{12}$$ ### 从 $\operatorname{Gamma}$ 函数到 $\operatorname{Zeta}$ 函数 $\operatorname{Gamma}$ 函数的定义（对 $\Re(s) > 0$）为： $$\Gamma(s) = \int_0^\infty t^{s-1} e^{-t} \, dt$$ 对它做一个变量替换 $t=nx$（$n$ 为正整数）可以得到： $$\Gamma(s) = n^s \int_0^\infty x^{s-1} e^{-nx} \, dx$$ 整理得： $$n^{-s} \Gamma(s) = \int_0^\infty x^{s-1} e^{-nx} \, dx$$ 对 $n$ 从 $1$ 到 $\infty$ 求和（在 $\Re(s) > 1$ 时收敛）： $$\Gamma(s) \sum_{n=1}^\infty n^{-s} = \int_0^\infty x^{s-1} \sum_{n=1}^\infty e^{-nx} \, dx$$ 进而得到 $\operatorname{Zeta}$ 函数的积分表示： $$\Gamma(s)\zeta(s)=\int_0^\infty \frac{x^{s-1}}{e^x-1}\,dx$$ ### 积分拆分为两部分 我们将积分拆成 $0 \to 1$ 和 $1 \to \infty$ 两段： $$\Gamma(s) \zeta(s) = \int_0^1 \frac{x^{s-1}}{e^x - 1} \, dx + \int_1^\infty \frac{x^{s-1}}{e^x - 1} \, dx$$ - 当 $s \to 0$ 时，第二项 $\int_1^\infty \frac{x^{s-1}}{e^x - 1} \, dx$ 是解析的（在 $s=0$ 附近无奇性）。 - 所有奇性都来自第一项 $\int_0^1 \frac{x^{s-1}}{e^x - 1} \, dx$。 ### 被积函数的展开 利用 $e^x - 1$ 的泰勒展开： $$e^x - 1 = x + \frac{x^2}{2!} + \frac{x^3}{3!} + \cdots = x \left(1 + \frac{x}{2} + \frac{x^2}{6} + \cdots \right)$$ 因此： $$\frac{1}{e^x - 1} = \frac{1}{x} - \frac{1}{2} + \frac{x}{12} - \frac{x^3}{720} + \cdots$$ 于是第一项积分变为： $$\int_0^1 x^{s-1} \left( \frac{1}{x} - \frac{1}{2} + \frac{x}{12} + \cdots \right) dx = \int_0^1 \left( x^{s-2} - \frac{1}{2}x^{s-1} + \frac{1}{12}x^s + \cdots \right) dx$$ 逐项积分（在解析延拓的意义下）： $$= \frac{1}{s-1}-\frac{1}{2s}+\frac{1}{12(s+1)}+x$$ $x$ 为在 $s$ 处解析的项 ### 提取 $s \to 0$ 时的奇性 我们设解析部分为 $w$。 当 $s \to 0$ 时： $$\Gamma(s) \zeta(s) = -\frac{1}{2s} + w$$ 而 $\operatorname{Gamma}$ 函数在 $s=0$ 处有一阶极点，其留数为 $1$： $$\Gamma(s) = \frac{1}{s} + \gamma + O(s)$$ 其中 $\gamma$ 是欧拉常数。 于是： $$\zeta(s) = \frac{\Gamma(s)\zeta(s)}{\Gamma(s)} = \frac{-\frac{1}{2s} + w}{\frac{1}{s} + \gamma + O(s)}$$ 当 $s \to 0$ 时，$\zeta(s) \to -\frac{1}{2} + O(s)$。 得到 $$\zeta(0) = -\frac{1}{2}$$ --- ### 利用函数方程得到 $\zeta(-1) $$\zeta(s) = 2^s \pi^{s-1} \sin\left(\frac{\pi s}{2}\right) \Gamma(1-s) \zeta(1-s)$$ 令 $s = 2$： $$\zeta(2) = 2^2 \pi^{1} \sin(\pi) \Gamma(-1) \zeta(-1)$$ 由于 $\sin(\pi) = 0$，这看起来像是 $0 \times \infty$ 的不定式。我们用极限来算。 利用 $\zeta(2) = \frac{\pi^2}{6}$，以及函数方程在 $s \to 2$ 时的极限行为，可以解得： $$\zeta(-1) = -\frac{1}{12}$$ ## 总结 虽然在写本文前作者对这部分内容有了解，但也有可能出错，欢迎指出。 本文参考 [百度对阶乘的简介](https://baike.baidu.com/item/%E9%98%B6%E4%B9%98/4437932) 和网上的全体自然数求和证明，如有违规，联系自删。 ## 修改记录 因作者对文章编写了解不足，故进行了多次修改，在此感谢指出问题的管理员们！ 本文先后修改了阶乘的写法、公式显示规范，若还有不足，欢迎指出，一定改进。