# Which is larger? $20!$ or $2^{40}$?

Someone asked me this question, and it bothers the hell out of me that I can't prove either way.

I've sort of come to the conclusion that 20! must be larger, because it has 36 prime factors, some of which are significantly larger than 2, whereas $2^{40}$ has only factors of 2.

Is there a way for me to formulate a proper, definitive answer from this?

Thanks in advance for any tips. I'm not really a huge proof-monster.

• There are $[n/2]+[n/2^2]+[n/2^3]+\dots =\sum_{k\geq 1}[n/2^k]$ factors of $2$ in $n!$. Where [$a$] is the floor function, i.e. greatest integer less than $a$. Combining this fact with some estimation of the other primes dividing $20!$ you should be able to get the result. Commented Nov 11, 2013 at 15:12
• Your "sort of" conclusion becomes a proof if you observe that at least 4 of those prime factors are at least twice as large as 2.
– Dan
Commented Nov 13, 2013 at 22:50

It is probably easier to note that $2^{40} = 4^{20}$. The only ones of the 20 factors in $20!$ that are smaller than $4$ are $1$, $2$ and $3$. But, on the other hand, $18$, $19$ and $20$ are all larger than $4^2$, so we can see $$20! = 1\cdot 2\cdot3\cdots 18\cdot19\cdot 20 > \underbrace{1\cdot1\cdot1}_{3\text{ ones}}\cdot\underbrace{4\cdot4\cdots 4\cdot 4}_{14\text{ fours}}\cdot\underbrace{16\cdot16\cdot 16}_{3\text{ sixteens}} = 2^{40}$$ by comparing factor by factor.

• +1, but $$1\cdot1\cdot1\cdot4\cdot4\cdots 4\cdot 4\cdot16\cdot16\cdot 16 =2^{24} \cdot 2^{12} \lt 2^{40}$$ Better $$1\cdot1\cdot1\cdot4\cdot4\cdots 4\cdot 4\cdot16 \cdots \cdot 16 = 2^{44} \gt 2^{40}$$ Commented Nov 11, 2013 at 15:27
• @miracle173: I think your arithmetic's off. How do you get $4^{14}$ to be $2^{24}$? Commented Nov 11, 2013 at 15:31
• because you added the braces after you read my comment. I assumed that $16 \cdot 16 \cdot 16$ was a lower bound for $16 \cdot 17 \cdots$ and $4 \cdot 4 \cdot 4 \cdots 4 \cdot 4$ is a lower bound for $4 \cdot 5 \cdot 6 \cdots 15$. Commented Nov 12, 2013 at 6:42

You can simply compute both numbers and compare them: $$20! = 2432902008176640000 \\ 2^{40} = 1099511627776$$

So you can easily see that $2^{40} < 20!$

• I would not be surprised if this answer was in negative votes. Commented Apr 27, 2016 at 8:11
• It seems this answer has gotten a lot of votes in both directions. But I, the asker, should have been more clear. Although I was looking for something more... elegant... I didn't specify this, so as it stands, this is a perfectly acceptable answer, and it has my upvote.
– Alec
Commented Mar 24, 2018 at 17:31

Use a multiplicative variant of Gauss's trick: $$(n!)^2 = (1 \cdot n) (2 \cdot (n-1)) (3 \cdot (n-2)) \cdots ((n-2) \cdot 3) ((n-1) \cdot 2) (n \cdot 1) \ge n^n$$ Setting $n=20$, we get $20!\ge 20^{10} > 16^{10} = 2^{40}$.

• It's worth adding how you know that $k(n-k+1)\ge n$. Commented Feb 24, 2017 at 18:39

Well we know that $\log_2 x$ is increasing so we could calculate

\begin{align} \log_2(20!) &=\log_2\left(\prod_{i=1}^{20}i\right) \\ &=\sum_{i=1}^{20}\log_2(i) \\ &=\log_2{1}+\log_2{2}+\log_23+\log_2{4}+\cdots+\log_2 8+\cdots+\log_216+\cdots+\log_2{20} \\ &>0+\log_2{2}+\log_2 2+\log_24+\cdots+\log_2{4}+ \\&\,\,\,\,\,\log_28+\cdots+\log_2{8}+\log_2{16}+\cdots+\log_2{16} \\ &=0+2\log_2{2}+4\log_2{4}+8\log_2{8}+5\log_2{16} \\&=0+2+4 \cdot 2+8 \cdot 3+5 \cdot 4 \\&=54 \\&>40=\log_2(2^{40}). \end{align}

Therefore, as $\log_2x$ is increasing we have $20!>2^{40}$.

In fact this shows that $20!>2^{54}$.

If we ignore the first terms of $20!$ we have $8 \times \dots \times 20$. That's at the very least $8^{13}$, which is $2^{39}$. Including the first factors we ignored we go over $2^{40}$.

Pretty ad-hoc, but just my 2 cents.

$$\frac{(20)!}{2^{40}}=\frac{(20)!}{4^{20}}=\frac14\cdot\frac24\cdot\frac34\cdot\frac44\cdots\frac{19}4\cdot\frac{20}4>\frac{3!}{4^3}\cdot\frac{19}4\cdot\frac{20}4=\frac{6\cdot19\cdot5}{64\cdot4}=\frac{570}{256}>1$$

That was a defensive approach

Observe that $\displaystyle\frac14\cdot\frac24\cdot\frac34=\frac3{32}>\frac1{11}$ which is compensated by $\displaystyle\frac84\frac94\cdot\frac{10}4=\frac{45}4>11$

$$\implies \frac{(20)!}{2^{40}}=\frac14\cdot\frac24\cdot\frac34\cdot\frac44\cdots\frac{19}4\cdot\frac{20}4>\frac14\cdot\frac24\cdot\frac34\cdots \frac84\frac94\cdot\frac{10}4>\frac1{11}\cdot\frac{45}4>1$$

i.e., $$\frac{(20)!}{4^{20}}> \frac{(10)!}{4^{10}}>1$$

Programmatically, I found $\displaystyle \frac{n!}{4^n}>1$ for $n\ge9$ which I think can be a good exercise

It is easy to compare these numbers using some basic analysis.

To approximate the numeric value of $20!$, use Stirling formula, which says that $20! \simeq (20/e)^{20} \sqrt{40 \pi}$. The usage of $\simeq$ here is a little vague; what the theorem actually says is that the ratio of the two is between $1$ and $1.08...$, which is more than enough for this application. Now, $20/e \simeq 7.35 \gg 4 = 2^2$, and the additional factor is greater than $1$, so you get: $$20! \gg (20/e)^{20} \gg 4^{20} = 2^{40}.$$

The sign $\gg$ is used a bit informally to mean 'is much greater than'. Feel free to replace it by simply $>$ if you like.

• How do you know that Stirling's approximation works well for $n$ as low as $20$?
– lhf
Commented Nov 11, 2013 at 15:16
• @lhf: the error in Stirling formula is bounded as explained in the edit. Commented Nov 11, 2013 at 15:20
• @lhf: also, Stirling's approximation offers a lower bound on $n!$, so showing that $(20 / e)^{20} > 4^{20}$ is enough to show that $20! > 4^{20}$. Commented Nov 11, 2013 at 20:56

From your statement that you know $20!$ has $36$ prime factors, you just need to note that there are four $5$'s and two $7$'s among them. Since $7 \gt 5\gt 2^2$ you have the four extra you need and are done.

You can also separate each one of these, into 10 terms and note:

$$1\times 20 > 2^4$$ $$2\times 19 > 2^4$$ $$\vdots$$ $$10 \times 11 >2^4$$ $$\Rightarrow 20! > 2^{40}$$

The idea is to break the factorial symmetrically into smaller pieces; which is not the most robust method for inequalities which include factorials; but it is useful in certain obvious cases.

• lhf did exactly this above. Commented Nov 11, 2013 at 21:49

I know I am beating a dead horse here, but anyways. If you can accept some "handwaving" this is an argument a normal higschool student should be able to accept. We have that if $a>b$ then $\log a > \log b$. Now when comparing big numbers, it is often easier to look at the logarithms. The crux here is to note that $$\log 20! > 20 \log(20)-20$$ Let us assume that $20!<2^{40}$, and see if we obtain a contradiction. \begin{align*} \log 2^{40} & > 20 \log(20)-20\\ 40 \log 2 & > 20(\log 5 + 2\log2)-20\\ 0 & > 20 \log 5 - 20 \\ 1 & > \log 5 \end{align*} Which is rubbish since $\log 5 > \log e = 1$. Therefore $$20! > 2^{40}$$ To see that $$\log n! > n \log n - n \ , \quad \forall \, n>0$$ One can note that $$\log n! = \sum_{k=1}^n \log k > \int_1^n \log x\,\mathrm{d}x = n \log n - n$$ Where the inequality comes from the following figure

• @dfeuer, I updated the figure it should be correct now =) Commented Nov 12, 2013 at 19:57
• Nice solution using Graph. Commented Nov 13, 2013 at 4:44

\begin{align}20!&=1\times2\times3\times2^2\times5\times(2\times3)\times7\times2^3\times3^2\times(2\times5)\times11\\&\,\,\,\,\,\,\times(2^2\times3)\times13\times(2\times7)\times(3\times5)\times2^4\times17\times(2\times3^2)\times19\times(2^2\times5)\\&=2^{18}\times3^8\times5^4\times7^2\times11\times13\times17\times19\\&>2^{18}\times2^8\times4^4\times4^2\times2^3\times2^3\times2^4\times2^4=2^{18+8+8+4+3+3+4+4}=2^{52}\\&>2^{40}\end{align}

$2^{40}= (2^{10})^4 = 1024^4 \approx (10^3)^4 = 10^{12}$

$20! = (20 \cdot 19 \cdot 18 \cdots 10) \cdot 9 \cdot 8\cdots 1 > 10^{11} \cdot 9 \cdot 8 \cdots 1 \gg 10^{12}$

By calculator you can see that $10! > 2^{20}$.
It is then easy to prove that for any $n >= 10$ that $n! > 2^{2n}$.
For intuitive purposes, just remember that on the left hand side you are multiplying by a growing number (larger than 10) and on the right hand side you are multiplying by 4.

$$\log _{10}\left( {2^{40} } \right)=40 \log _{10}\left( {2} \right)= 12,04$$ so the numbers of digits of $$2^{40}$$=13

$$\log _{10}\left( {20! } \right)=\sum _{1}^{20} \log_{10} \left({x})\right)=18,38$$ so the numbers of digits of 20! Is $$19$$

So $$20!>2^{40}$$

With Stirling's formula:

$$4^n \lt \sqrt{2 \pi n} \left(\frac{n}{e}\right)^n \le n! \le e \sqrt{n} \left(\frac{n}{e}\right)^n$$

Both $\le$ are valid for $n\ge1$. Because $e\le 3$ the left inequality is valid a least for all $n \gt 12$.

• +1 for using irrational numbers. It's like using a medieval broadsword to slice a pizza. Commented Oct 7, 2021 at 14:15

Here's my take on this:

First find the number of factors of 2 in 20! This can be done with

$\left\lfloor \frac{20}{2^{1}} \right\rfloor\; \; +\; \left\lfloor \frac{20}{2^{2}} \right\rfloor\; +\; \left\lfloor \frac{20}{2^{3}} \right\rfloor\; +\; ...\; +\; \left\lfloor \frac{20}{2^{5}} \right\rfloor\; \; \;$

Computing this you get there are 18 factors of 2.

Next, find the factors of 3. Using the same method as above except taking powers of 3 instead of powers of 2 you get that there are 8 factors of 3. Each factors of 3 is about 1.5 factor of 2 because $\log_2(3) = 1.5$ so it is like there are 8*1.5 = 12 additional factors of 2.

Next do the same for factors of 5. There are 4 factors of 5, but each factor of 5 is about 2.3 factors of 2 (from $\log_2(5)$) so it is like there are 4*2.5 = 10 extra factors of 2.

In total there are now 18 + 12 + 10 = 40 factors of 2. There will be even more as you can also take 7, 11, 13, 17, and 19 as primes, so it is now clear that 20! is much larger.

• Your 'each factor of 3 is like 1.5 factor of 2' is actually kind of close, but the analysis is wrong. Remember that you're working with exponents - your claim would be that 'each factor of 7 is like 3.5 factors of 2', but in fact two factors of 7 multiply out to 49, whereas 2*3.5 = 7 factors of two (which would be 'equivalent' by your argument) multiply out to 128. Commented Nov 11, 2013 at 22:12
• You're right - I should have used log base 2 instead. Commented Nov 12, 2013 at 1:43
• This is what the 'edit' button is for. :-) (But unfortunately, many people won't have logs of 3 and 5 memorized offhand...) Commented Nov 12, 2013 at 1:56
• You can just estimate to the nearest integer and it should still work fine. Commented Nov 12, 2013 at 6:29

$20!=1*2*3*4*5*6*7*8*9*10*11*12*13*14*15*16*17*18*19*20$

$20!=2^{1+2+1+3+1+2+1+4+1+2=18}*3^{1+1+2+1+1+2=8}*5^{1+1+1+1=4}*7^{1+1=2}*11^{1}*13^{1}*17^{1}*19^{1}$

$20! \gt 2^{18+8+4+2+1+1}*17^{1}*19^{1}\gt2^{34}*16*16=2^{34}*2^4*2^4>2^{42}>2^{40}$

Hence $20!\gt2^{40}$

I think this is very easy to think...

20!=2^18 . 3^8 . 5^4 . 7^2 . 11.13.17.19 > 2^40

taking log with base 2 on both sides (log used anytime after this is with base 2)

18+8log3+4log5+2log7+log11+log13+log17+log19 > 40

1<log3<2

2<log5<log7<3

3<log11<log13<4

4<log17<log19<5

Hence even if we take values on the lower side of the inequality:

18+ 8(1)+ 4(2)+ 2(2)+ 3+ 3+ 4+ 4 > 40

52>40

Hence 20!>2^40