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

发表于 更新于 分类于 阅读次数： 本文字数： 4.5k 阅读时长 ≈ 4 分钟

By Long Luo

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

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

function graph

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

但具体哪个更大呢？

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

对数放缩法 (Zoom)

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

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

左边：

A=log⁡2(2100!)=100!A = \log_{2}{(2^{100!})} = 100!

右边：

B=log⁡22100!=log⁡22100+log⁡2(2100−1)+⋯+1+0B = \log_{2}{2^{100}!}= \log_{2}{2^{100}} + \log_{2}{(2^{100} - 1)} + \dots + 1 + 0

共有 21002^{100} 项，值从 00 到 log⁡22100=100\log_{2}{2^{100}} = 100 ，所以

B<100⋅2100<128⋅2100=27⋅2100=2107B < 100 \cdot 2^{100} < 128 \cdot 2^{100} = 2^7 \cdot 2^{100} = 2^{107}

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

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

显然可得 100!≫2222≫2107100! \gg 2^{222} \gg 2^{107} 。

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

斯特林公式 (Stirling’s Approximation)

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

n!∼2πn(ne)n=2πnn+12e−nn! \sim \sqrt{2 \pi n}(\frac{n}{e})^n = \sqrt{2 \pi} n^{\frac{n + 1}{2}}e^{-n}

两边同取对数：

ln⁡n!∼12ln(2π)+(n+12)ln(n)−n\ln{n!} \sim \frac{1}{2} ln(2 \pi) + (n+\frac{1}{2}) ln(n) - n

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

ln⁡(n!)∼n(ln(n)−1)\ln(n!) \sim n(ln(n) - 1)

则有：

A=ln(2100!)=100!ln(2)B=ln(2100!)∼2100(ln(2100)−1)=2100(100ln(2)−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}

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

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

2100!≫2100!2^{100!} \gg 2^{100}!

数列法

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

我们可以构建一个序列：

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

只需要判断 FnF_n 是否大于 11 即可。

当 n=1n = 1 时，

F1=21!(21)!=21(2)!=22=1F_1 = \frac{2^{1!}}{(2^1)!} = \frac{2^{1}}{(2)!} = \frac{2}{2} = 1

当 n=k+1n = k + 1 时，

Fk+1=2(k+1)!2k+1!=Fk⋅2(k+1)!−k!2k+1⋅(2k+1−1)⋯(2k+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)}

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

所以：

  1. 当 (n+1)!−n!<n2n(n + 1)! - n! < n2^n , An+1<AnA_{n+1} < A_n ；
  2. 当 (n+1)!−n!>(n+1)2n(n + 1)! - n! > (n + 1)2^n , An+1>AnA_{n+1} > A_n 。

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

简单计算下前 77 项的值：

F2=0.25F3=0.0015⋯F4=8.018⋯×10−7F5=5.05⋯F6=4.34⋯×10127F7=4.02⋯×101301\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}

可以看出， A100=A7⋅8⋅8!9⋅28⋯100⋅100!101⋅2100A_{100} = A_7 \cdot \frac{8 \cdot 8!}{9 \cdot 2^8} \cdots \frac{100 \cdot 100!}{101 \cdot 2^{100}} 。

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

简洁法

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

n!=1×2×⋯nn! = 1 \times 2 \times \cdots n ，而 nn=n×n×⋯nn^n = n \times n \times \cdots n 。

n>2n > 2 , nn≫n!n^n \gg n! 。

因此：

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

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

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

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

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

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

100!=250⋅225⋅212⋅26⋅23⋅2⋅332⋯520⋯11⋯97=297⋅11⋅13⋯97≫210⋅297=2107\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}

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

参考文献

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

  2. Logarithm ↩︎

  3. Stirling’s Approximation ↩︎