哪个更大呢？ 2^100! 还是 (2^100)! ？

By Long Luo

昨天在B站看到一个数学视频^[1]，比较 $2^{100!}$ 和 $2^{100}!$ 的大小。直观感受就是这2个数都非常非常大，但哪个更大无法一眼看出来。

虽然指数爆炸，但阶乘实际上增长的速度比指数更快，如下图1所示：

可以看出阶乘图像 $y = x!$ 实际上比指数 $y = e^x$ 要快很多，而 $y = x^x$ 是最快的。

但具体哪个更大呢？

这个问题有很多种方法，这里展示了4种方法。

对数放缩法 (Zoom)

由于对数^[2] 函数 $y = \log_{a}{b}$ 当 $a > 1$ 是单调递增函数，所以比较两个数大小时，可以通过比较两者对数值来实现大小比较。

两边同取对数 $\log_{2}{x}$ ，

左边：

$$A = \log_{2}{(2^{100!})} = 100!$$

右边：

$$B = \log_{2}{2^{100}!}= \log_{2}{2^{100}} + \log_{2}{(2^{100} - 1)} + \dots + 1 + 0$$

共有 $2^{100}$ 项，值从 $0$ 到 $\log_{2}{2^{100}} = 100$ ，所以

$$B < 100 \cdot 2^{100} < 128 \cdot 2^{100} = 2^7 \cdot 2^{100} = 2^{107}$$

综合上式，我们只需要比较 $100!$ 和 $2^{107}$ 的大小即可。

$100!$ 至少有 $(100 - 64 + 1) = 37$ 项是大于等于 $64 = 2^6$ ，也就是 $(2^6)^{37}=2^{222}$ 。

显然可得 $100! \gg 2^{222} \gg 2^{107}$ 。

故有虽然两个数都非常大，但 $2^{100!}$ 仍然远远大于 $2^{100}!$ 。

斯特林公式 (Stirling’s Approximation)

由于存在阶乘，我们可以使用斯特林公式(Stirling’s Approximation)^[3] 来估计。

$$n! \sim \sqrt{2 \pi n}(\frac{n}{e})^n = \sqrt{2 \pi} n^{\frac{n + 1}{2}}e^{-n}$$

两边同取对数：

$$\ln{n!} \sim \frac{1}{2} ln(2 \pi) + (n+\frac{1}{2}) ln(n) - n$$

根据上式，可见 $n$ 足够大时，斯特林公式可以近似为：

$$\ln(n!) \sim n(ln(n) - 1)$$

则有：

$$\begin{array}{l} A = ln(2^{100!}) = 100! ln(2) \\ B = ln(2^{100}!) \sim 2^{100}(ln(2^{100}) - 1) = 2^{100}(100 ln(2) - 1) \end{array}$$

由于 $2^{10} = 1024 \approx 10^3$ ，则有 $2^{100} \approx 10^{30}$ , 那么 $B \approx 10^{32} ln(2)$ 。

很明显 $100! \gg 10^{32}$ ，因此

$$2^{100!} \gg 2^{100}!$$

数列法

对于任意正整数 $n$ ，比较 $2^{n!}$ 和 $(2^n)!$ 的大小。

我们可以构建一个序列：

$$F_n= \frac{2^{n!}}{(2^n)!}$$

只需要判断 $F_n$ 是否大于 $1$ 即可。

当 $n = 1$ 时，

$$F_1 = \frac{2^{1!}}{(2^1)!} = \frac{2^{1}}{(2)!} = \frac{2}{2} = 1$$

当 $n = k + 1$ 时，

$$F_{k + 1} = \frac{2^{(k + 1)!}}{2^{k + 1}!} = F_k \cdot \frac{2^{(k + 1)! - k!}}{2^{k + 1} \cdot (2^{k + 1} - 1) \cdots (2^k + 1)}$$

分母中的阶乘项刚好是 $2^n$ 项，每项取值范围 $[2^n, 2^{n+1}]$ ，所以分母取值范围： $[(2^n)^{2^n} = 2^{n2^n}, (2^{n + 1})^{2^n} = 2^{(n + 1)2^n}]$ 。

所以：

1. 当 $(n + 1)! - n! < n2^n$ , $A_{n+1} < A_n$ ；
2. 当 $(n + 1)! - n! > (n + 1)2^n$ , $A_{n+1} > A_n$ 。

因为 $(n + 1)! - n! = (n + 1)n! - n! = n \cdot n!$ ，当 $n > 2$ 时， $n! > 2^n$ ，那么 $n$ 大于某个值时， $F_{n + 1} > F_n$ 。

简单计算下前 $7$ 项的值：

$$\begin{array}{l} F_2 = 0.25 \\ F_3 = 0.0015\cdots \\ F_4 = 8.018\cdots \times 10^{−7} \\ F_5 = 5.05\cdots \\ F_6 = 4.34\cdots \times 10^{127} \\ F_7 = 4.02\cdots \times 10^{1301} \\ \end{array}$$

可以看出， $A_{100} = A_7 \cdot \frac{8 \cdot 8!}{9 \cdot 2^8} \cdots \frac{100 \cdot 100!}{101 \cdot 2^{100}}$ 。

故 $2^{100!}$ 比 $(2^{100})!$ 是超出想象的大。

简洁法

由图1显然 $n! < n^n$ ，也很容易证明。

$n! = 1 \times 2 \times \cdots n$ ，而 $n^n = n \times n \times \cdots n$ 。

$n > 2$ , $n^n \gg n!$ 。

因此：

$$B = (2^{100})! < (2^{100})^{2^{100}} = 2^{100 \cdot 2^{100}}$$

进一步放缩，由 $100 < 128 = 2^7$ ，故有

$$B = (2^{100})! < 2^{2^{107}}$$

很明显 $2^{107} < 100!$ ！

这里用公因子方法来证明：

由于 $100 = 2 \cdot 50 = 4 \cdot 25 \ge 8 \cdot 12 \ge 16 \cdot 6 \ge 32 \cdot 3 > 64$ ，可得：

$$\begin{array}{l} 100! = 2^{50} \cdot 2^{25} \cdot 2^{12} \cdot 2^6 \cdot 2^3 \cdot 2 \cdot 3^{32} \cdots 5^{20} \cdots 11 \cdots 97 \\ = 2^{97} \cdot 11 \cdot 13 \cdots 97 \\ \gg 2^{10} \cdot 2^{97} = 2^{107} \\ \end{array}$$

所以 $2^{100!} \gg (2^{100})!$ 。

参考文献

---

1. 比较大小，看起来很像! ↩︎

2. Logarithm ↩︎

3. Stirling’s Approximation ↩︎