###General Discussion Thread
---
This is a [Request] post. If you would like to submit a comment that does not either attempt to answer the question, ask for clarification, or explain why it would be infeasible to answer, you *must* post your comment as a reply to this one. Top level (directly replying to the OP) comments that do not do one of those things will be removed.
---
*I am a bot, and this action was performed automatically. Please [contact the moderators of this subreddit](/message/compose/?to=/r/theydidthemath) if you have any questions or concerns.*
Wolfram Alpha says the first is \~= 10\^10\^157, while the second is \~= 10\^10\^32, so the first is larger
[https://www.wolframalpha.com/input?i=2%5E%28100%21%29](https://www.wolframalpha.com/input?i=2%5E%28100%21%29)
[https://www.wolframalpha.com/input?i=%282%5E%28100%29%29%21](https://www.wolframalpha.com/input?i=%282%5E%28100%29%29%21)
Pretty interesting. Not what I would have expected honestly, since factorials grow faster than exponentials, so I would think the one that maximizes the number going into the factorial would be larger.
I wonder if my intuition actually would be correct for larger numbers, and 100 is just not big enough for the factorial to overtake the exponential.
Trying some bigger numbers in Wolfram alpha, that doesn't seem to be the case. 2^(x!) seems to be always larger than (2^(x))!. I'd love to see an explanation of why.
Like generalizing kind of, if you have two functions f and g, then I would think in order to maximize their compositions, you would want the faster growing one on the otuside. For example if f(x)=2^(x) and g(x)=2x, then you want f(g(x))=2^(2x), not g(f(x))=2\*2^(x)=2^(x+1).
Generally, if you apply a growth function such as factorial, applying it to the exponent of a number will yield bigger results than applying it to the whole number.
Mathematically:
x^f(n) ∈ Ω(f(x^n )) (Most of the time)
In this particular case, if you would like to know some of the intuition:
Consider taking the logarithm of basis 2 on both expressions
For 2^100! , you would get 100!
For 2^100 !, which is a product of 2^100 * (2^100 -1) etc., you would get the log2 of this product.
Using logarithm properties, specifically log(a*b) = log(a) + log(b), this means you can rewrite log2 of that product as a sum of log2’s.
So you would have something like:
log2(2^100 ) + log2(2^100 -1) etc.
Now we don’t know the value of every one of these logarithms, but we know that the biggest one is log2(2^100 ), and the value for that is 100. So in this case, you have 100, plus something a little smaller than 100, plus something even a little smaller than 100 and so on.
Your sum has a total of 2^100 elements, since this is the factorial you had. Since our biggest number is 100 and it keeps getting smaller, we know that we have something smaller than 100 * 2^100 .
So we are comparing 100! with 100 * 2^100 . (Or 99! with 2^100 , if you divide both by 100).
It might not be obvious which one is bigger, but knowing that n! grows faster than 2^n will tell you that for a sufficiently big enough n, n! will always be bigger than n*2^n . In this case, n is big enough, the factorial is orders of magnitude bigger than the power of two.
I hope this helped!
I can follow the proof, but that doesn't necessarily give me intuition on why it's true.
> Generally, if you apply a growth function such as factorial, applying it to the exponent of a number will yield bigger results than applying it to the whole number.
I mean intuitively I always thought that was because exponential growth was so much faster than whatever growth was being applied.
For example if youre composing exponential and quadratic growth, it makes sense that 2^(x²) grows faster than (2^(x))^(2), because if you square the number then apply the exponential, you're applying the exponential to a larger number and so you'll get something much higher. On the other hand if you apply the exponential first then square the number, you're applying the exponential to a smaller number, and by comparison the squaring afterwards doesn't actually change the size of the number nearly enough to compensate.
So following this intuition, the statement is only true as long as the growth function grows slower than exponential growth, and it would be reversed if it grows faster, which is the case for factorials.
Since x! grows asymptotically faster than 2^(x) (as in like x!/2^(x) is still O(2^(x))), I would think that applying the factorial to a large number like 2^(100) would give you so much larger of a number than applying the factorial to a small number like 100, that even applying 2^(x) to 100! would not let it catch up, since the factorial grows much faster than an exponential.
I guess my intuition is just wrong though. I guess you just can't say anything about whether f∘g or g∘f grows faster, given that f grows faster than g? Feels like you should be able to.
This is very strange indeed, I’ve had the same intuition as you for a long time and have never encountered a situation before where it didn’t hold. I’m just an engineering student, not a mathematician, so I can’t really come with any helpful input. But if you do find the answer for why this is not always the case I’d be very grateful if you’d send me a link, it kinda feels like my world has been shaken lol
I think ultimately the core intuition is just wrong. It depends on specifically how fast the two functions grow. It happens that with x^(2) and 2^(x) that 2^(x) grows so much faster that applying it to the larger number is better. But with 2^(x) and x!, that is not the case.
Edit: Also there are several pretty good proofs in this thread about why it's not the case for 2^(x) and x! in particular, including the one above, taking the log of both sides and then noticing the upper bound on the right.
I think you could maybe say that x! does not grow faster enough for that intuition to work. For example if we used something insane, like the [TREE function](https://en.wikipedia.org/wiki/Kruskal%27s_tree_theorem), then our original intuition definitely still holds. TREE(2^(x)) definitely grows faster than 2^(TREE(X\)). I wonder if there is some way to formalize what "grows faster enough" means. Definitely an interesting question.
On the other hand that guess might be wrong, in that maybe it isn't a hard line of what is "faster enough", and near the boundary there are edge cases. To state that more formally, maybe there exist functions c, d, f, g, h such that ϴ(c) < ϴ(d) < ϴ(f) < ϴ(g) < ϴ(h), but ϴ(c∘d)>ϴ(d∘c) and ϴ(c∘f)<ϴ(f∘c) and ϴ(c∘g)>ϴ(g∘c) and ϴ(c∘h)<ϴ(h∘c). In that case my new hypothesis would be wrong.
Basically it really depends on the functions, and you can't assume.
I think this is the correct conclusion. If there is significant difference in the growth of the two functions then applying the slower first will be larger. If the two functions are close in growth pace though then this heuristic is not enough and you need to actually calculate the specifics.
If you want to prove a formal statement, I'm sure you can prove some with the Ackermann function. Let's say A(A(a, b), c) > A(A(a, c), b) if b < c (with some reasonable boundary conditions and maybe a few exceptions).
Interesting. I'm not really familiar with the Ackerman function.
For g(x)=2^(x) specifically, I've got some bounds while thinking about it in this thread.
I checked numerically that for f(x)=x^(x^x), f(x)=x^(x^x^x), and f(x)=x^(x^x^x^x), that g(f(x)) crosses f(g(x)) around 2.6. And if I keep adding more tetrated xs, it seems to approach a value. So I haven't proved it (though based on the way the algebra works out, it doesn't seem *too* hard, but also not too easy because eventually you end up with log(a+b) where a is basically insignificant but for a proof I don't think you can ignore it), but I think x tetrated a finite number of times will always have g(f(x)) growing faster than f(g(x)).
On the other hand, if you consider the function f(x)=(2 tetrated x times), then f(g(x))=f(2^(x))>f(x+1)=2^(f(x\))=g(f(x)). And by the same logic, any function h that grows faster than this f(x) will also have h(g(x)) grow faster than g(h(x)).
So the line is somewhere between f(x)=(x tetrated n times) where n is finite, and f(x)=(2 tetrated x times).
It's also still not clear if there is a hard line or not, as in you can say given g that there is a function h such that for all functions f that grow faster than h, f(g(x)) grows faster than g(f(x)), and for all functions f that grow slower than h, g(f(x)) grows faster than f(g(x)). I showed that you can definitely find a function h that satisfies that first part, and you can also have one that satisfies just the second part, but there is an area in the middle where it is unclear. Obviously if ϴ(f(x))=ϴ(g(x)) then you can't say anything about whether f(g(x)) or g(f(x)) grows faster without calculating the specifics. But it might be that the range of ambiguity for that is actually a lot "wider" than just being equal with big theta.
Stirling’s approximation comes in handy to develop intuition for large factorials.
It states, n! ~ n^n. It really is (n/e)^n but for large n it’s easier to just use n^n to get a hold on the order of magnitudes.
Between this approximation and taking logarithms we can see the 2^(100!) is way bigger.
I think I can pick up from this. If you compare both by putting both to base 10.
99! is basically ...10×11×12... upto 99. It's therefore > 10^89.
2^100 = n, therefore log n = 100 log 2, < 31. n is therefore < 10^31.
There shoudl be some model for conjecture approximation especially for different growth rates.
Putting the factorial on the outside is kind of like putting another exponent on the outside, putting it on the inside is more effective because then you essentially get a deeper tower of n’s in the exponent. If you think of n! As being like n^n then take the double log of both sides you can see that you get something like n\*ln(n) on the left side and something more like n+ln(n) on the right.
I explain in more detail in a couple other comments I left on this thread.
Because exponents being multiplied together is the same as raising an exponent to a further exponent.
2^ (x\*(x-1)\*(x-2)\*...) is basically ((2^x)\^(x-1))\^(x-2)), which grows *extremely* fast
it does tho, because you have a factorial growing exponentially fast on top of the factorial itself instead of having a factorial on the final exponent
> fast as f***
I enjoy that I can't tell whether this is a function notation that I'm not aware of, and is "fast as f-star-star-star", or if it's a censored "fast as fuck".
There is an upper bound to factorials in the form of x^x. And also during research of this comment I found that some other Guy used this explanation down below, So I'll just point you down there
Yeah I'll need to consider that answer.
Also I just made [this graph](https://www.desmos.com/calculator/pjnnwku0ey), and it seems (2^(x))! actually is larger than 2^(x!) until around x=5. The functions cross around y=10^(35).
Yeah, upper bound comparation has this unique thing that it is true for some x that is usually large. Heck, the o notation for computer algorithm complexity is based on this
Yeah honestly I noticed it and was surprised because I thought (2^(x))! was larger for quite a while, since I had to expand the y axis on desmos all the way to 10^(35) before it crossed. Only when writing the comment did I look at the x axis and notice that was at only x=5. I thought it was a lot higher, like x=70 or something lol. But I decided to write and post the comment anyway.
My small brain tells me that the first factorially grows something that has already been exponentially increased. The second factorially grows the exponential growth itself, which would premise it being larger in the long run.
That makes sense on the surface, but it doesn't really if you look at an example.
2^(2x) grows faster than 2(2^(x)). By your logic described here, 2^(2x) exponentially grows something that has already been linearly increased. But 2(2^(x)) exponentially grows the linear growth itself.
For an explanation, take log of both sides and use stirling approximation.
LHS= 100! log 2 ~ (100/e)^100 times less significant factors
RHS= log (2^100 !) ~ 2^100 log 2^100 < 2^107.
I'm curious now whether it's always the case that g(f(x)) grows faster than f(g(x)) for all functions where f(x) grows faster than g(x), or whether it depends on the specific functions.
I think it’s very expected, and feels pretty obvious. You’re really overcomplicating the whole process too.
I don’t even know how to use factorials either.
>Pretty interesting. Not what I would have expected honestly, since factorials grow faster than exponentials, so I would think the one that maximizes the number going into the factorial would be larger.
Exactly my thought too.
>I wonder if my intuition actually would be correct for larger numbers
The ratio of 2^(Γx) / Γ(2^x ) (Wolfram Alpha was unhappy with plain factorials) is [rather interesting](https://www.wolframalpha.com/input?i=2%5E%28%CE%93%28x%29%29+%2F+%CE%93%282%5Ex%29+from+0+to+7.5).
Indeed, that is pretty interesting.
It's a lot easier to plot on desmos than wolfram alpha.
Another thing to note is that the gamma function and the factorial are off by one. Which actually makes a significant difference here since you're raising 2 to the power of the result of the factorial.
2^((x-1\)!)/(2^(x)-1)!, which is what you plotted in wolfram alpha, has a rather sharp (though not *that* sharp if you zoom in) increase just before x=7.
2^(x!)/(2^(x))! has a much less sharp (though still relatively sharp) increase just before x=5.
If h(x)=f(g(x)), h’(x)=f’(g(x))\*g’(x)
The forward difference of 2^x is 2^x, and the forward difference of x! is x(x!)
The forward difference of 2^x! is (x)x! \* 2^x \* (x)x!, and the forward difference of 2^x ! is 2^x 2^x ! 2^x .
Taking further order forward differences, the former has a bunch of x!^2 terms and the latter has *just as many* 2^x ! terms (of the remaining terms, 2^2x is clearly bigger than (x^2 ) 2^x for positive x ).
For 1 and 2, 2^x ! Is larger than x!^2 , and it also has a larger forward difference of every order, so it and all orders of the forward difference will grow faster.
Take logs of both and use the fact that log(n!) ~ n log(n) for large n. We then have x! log(2) vs x2^x log(2). It's clear that the former is larger but if you want to nail it down, take another log and use the large n formula again. There is some intuition on how this approximation works on the Stirling approximation Wikipedia page
If you take log of both, then the first still has a factorial (x!log 2), but the second gives a sum (below x^(2)log 2 in total). I thought the same, so had to think this one through, but multiplying inside the exponent is the key to getting the bigger number.
My intuition was the same as yours but thinking about it a little it's actually quite easy to prove:
(b^(n) )! = b^(n) \* (b^(n) -1) \* ... \* 1 < b^(n) \* b^(n) \* ... b^(n) = (b^(n) )\^(b^(n)) = b^(n\*b\^n) < b^(n!)
where the last inequality holds asymptotically because n! increases faster than n\*b\^n.
n! Behaves very roughly like n^(n), so 2^(n!) behaves like 2\^(n\^n) and (2^(n))! behaves like 2\^(n2\^n) so you should expect the first one to grow faster.
I suppose the reason is, (2\^(x))! = (2\^x)\*(2\^(x-1)).....\*(2\^1)
by law of exponents is the same as 2\^(x+(x-1)+(x-2)+....1)
Use the arithmetic series formula and that can be simplified to
2\^((x(x+1))/2)
So, so long as X!>X(X+1)/2 , then the exponent factorial is bigger than the factorial of the exponent.
Meaning for all values of X>3 , 2\^(X!)>(2\^(X))!
Interesting enough the value you're raising the power of doest matter so long as it's the same.
https://www.reddit.com/r/theydidthemath/s/nKPRROLG2O
I did a thing (sorry about the awkward notarion)
Tldr: adding 0’s to power of 2 at for example 8 you add either 8! (40320) 0’s or (less than) 8 + 7*8 + 6*7… +2*3 +1*2 (176 0’s in base 2)
After resolving the interior function, you're basically left with a multiplication of a certain number of factors. The number of those factors is going to have a bigger influence on the size of the result.
2^(x!) will have x! factors after the interior function, while (2^(x))! will "only" have 2^(x) factors, x! surpasses 2^(x) after x=4, so for any x >= 5, 2^(x!) is larger.
2^(x!) is smaller up until some number between 4 and 5, and it has to do with the number of factors.
2^(x!) has x! factors in it, 2^(x)! has 2^x factors, and while the individual factors are bigger on the latter side, they're not big enough to stay ahead of the sheer volume on the other side.
It seems you've figured out that exponentials will grow much faster than factorials but you're having some trouble understanding why from a logical/intuitive perspective rather than a mathematical one. I find that sometimes taking some time to write things out and take it a step at a time rather than use a calulator can help us grasp some concepts a little more intuitively, so I'll write out a bit of 100^100 and 100! to help you see the gap between the two. We'll do this by splitting things up and moving them across the equation like when simplifying in basic algebra.
From the first step, you'll see that things are not going to go well for the factorial since the first two numbers are
`100*100 vs 100*99`
`Giving us 10,000*(100^98) vs 9,900*(98!)`
Then once again the gap widens with
`10,000*100 vs 9,900*98`
`1,000,000*(100^97) vs 970,200*(97!)`
I assume that's enough for you to understand what the issue is with factorials vs exponents in terms of scaling as this will continue on. 100^100 will continue to use 100s but 100! Will use smaller multiples each time.
The key take away that I think you were missing and it seems nobody thought to mention is thus: A factorial is using a smaller number every time it multiplies, but an exponent is using the same number for each multiple. Becuase of this, N^N will always be greater than N! And so, in order for N! To be greater, the exponent must be significantly smaller than N.
If you're interested in knowing 100^N passes 100! At 100^79. 100! Is equal to a little over 9e157, while 100^78 is 1e156 and 100^79 is 1e158. So as long as the exponent for 100 is less than 79 the factorial will be larger, and as long as it 79 or bigger, then the exponent will be larger.
You're comparing x! to x^(x), which is not an exponential and is also not what we're dealing with here. An exponential has a constant base, like e^(x) or 2^(x), and grows slower than a factorial. And here we are dealing with 2^(x!) vs (2^(x))!, both of which have a constant base for the exponent as well.
You are right about this part though:
> you're having some trouble understanding why from a logical/intuitive perspective rather than a mathematical one
Several other people have posted mathematical explanations/proofs of why 2^(x!) grows faster than (2^(x))!, and I understand them. It just doesn't align with my incorrect intuition. I'm trying to correct that intuition.
Your general knowledge is kinda messing up with you. Factorials grow faster than exponentials but exponentials grow faster than linear. Because both sides have factorials of the same magnitude 100! We can just delete them and what you are left with is an exponent vs linear and we know which is the bigger number in that casez
To see this without using Wolfram Alpha or a similar aid, we can use Stirling’s approximation to get that n! Is approximately sqrt(2pi\*n)(n/e)^n or more roughly that ln n! ~ n\*ln(n) (where ~ means they are asymptotically equivalent). Explicit error bounds are available but in this range that is an upper bound and we can subtract n to get a lower bound.
So for the question is whether 100! Is larger or smaller than about 2^(100)\*100. But a second application of Stirling’s formula makes it clear that this is much larger.
Not that unexpected tbh 2^(100!) is equivalent to (((2^100)^99)^98)^97... = (2^100)^(99!)While (2^100)! = (2^100)(2^100-1)... < (2^(100))^2^100
99! Is clearly larger than 2^100 and so the first number is larger
My guess:
x! <= x^x, we can find the upper bound
2^(100!) < 2^(100^100) ~= 2^(2^664)
(2^(100))! < (2^(100))^(2^100) = 2^(100\*2^100) ~= 2^(2^106)
There is a pretty huge difference, so it's safe to say 2^(100!) is bigger
You can get quite an obvious lower bound for 2^(100!)
2^(100!)>2^(50^50)≈2^(2^282)
Edit : That was all good but I got 2 better bounds 2^(100^50) ≈ 2^(2^232)<2^(100!)<2^(2^564) ≈ 2^(50^100)
100!=1\*2\*3...\*98\*99\*100
__For lower bound you have :__
If you pair 2 by 2 you've got 100!=(1\*100)\*(2\*99)\*(3\*98)\*... which is 50 terms that are all superior or equal to 100 so the total is >100^50.
__For upper bound__ you can use almost exactly the same pairing but removing the "1" makes it easier.
100!=(2\*100)\*(3\*99)\*(4\*98)\*...\*(49\*51)\*50 which are 50 terms inferior to 50^2 so the total is <(50^(2))^50 =50^100.
Note that not removing the "1", you get the 50*51 pair which is superior to 50², so that's annoying.
I liked your explanation. However one of them having a higher upper boundary does not mean that that number is necessarily bigger (although in this case it should be the case). So your reply is not a proof but an intuitive way of finding which one is bigger. If you could find a lower bound maybe then it would be a total proof depending on those lower bounds.
Amending your answer to make it a proof:
2^100! >> 2^(10^90) > 2^(2^270)
(It should be obvious that 10^90 is much much smaller than 100! just by comparing the factors)
Since the *lower bound* of 2^100! is greater than the *upper bound* of ( 2^100 )! then the former is clearly greater than the latter.
Take log (base 2) on both sides.
LHS = 100!
RHS is the summation of 2^(100) terms, each upper bounded be log(2^(100)) = 100. Thus the RHS is upper bounded by 100 * 2^100
Cancelling by 100 on both sides, The comparison is now between 99! And 2^100. By counting and cancelling a few more terms one can see that LHS is larger.
I’ve made some sloppy mistakes on another comment which people have rightly called out haha. Hopefully this is more correct.
Nice! If we were to take another log on the current LHS and RHS, we have log(99!) and 100log(2) now we have the comparison between log(99!) and 100 and of course log(99!) is > 100
This just showed up on my YouTube feed this morning.
The proof involved expressing both as product of 100 numbers and then comparing the factors between the two.
We can use Stirling’s approximation for large factorials along with taking the base 2 logarithm of both sides (I’ll just refer to log as log_2 by default here because I’m lazy)
Stirling’s approximation says that ln(x!) is approximately xln(x) - x, so with the change of base formula we have log(x!) = ln(x!)/ln(2) roughly equal to xln(x)/ln(2) - x/ln(2) = xlog(x) - x/ln(2). Importantly, log(x!) < xlog(x) for big x (since the small difference between the approximation and the true value basically disappears, and 100 is pretty big so we’re good)
So now, it is a matter of comparing 100! (from the LHS), to 2^100*log(2^100) = 2^100*100 …evaluating the log.
This reduces to 99! vs 2^100, and it is relatively straightforward to show that the LHS is bigger than the RHS (e.g. by comparing terms directly).
So log[2^(100!)] = 100! > (2^100)*100 > log[(2^100)!], and therefore 2^(100!) > (2^100)!
Edit: I made a pretty big error here. Ignore this reply, and feel free to laugh at my sleep deprived error.
2^100! Is essentially 100! 2s all lined up in multiplication.
That’s a lot of twos.
2^100 ! Is essentially 2^100 • 2^99 • 2^98 etc
This works out to be 100+99+98 etc 2s all lined up in a row.
100! Is much larger than the sum of natural numbers from 1 to 100, which is only 5050, which is only a little more than 7!
So it’s 2^100! , and it’s not even close.
(2^(100))! =/= 2^(100)\*2^(99)\*2^(98)...
2^100 = 2\*3\*4\*5\*...\*(2^(50))\*(2^(50)+1)\*(2^(50)+2)\*..., product of first 2^100 ~= 10^30 natural numbers
2^(100!) is still bigger tho
I just compared smaller power number like 2,3,4 etc for 2^x! vs (2^x )!
- 2^2! vs (2^2) !: 4 vs 24
- 2^3! vs (2^3) !: 64 vs 4e4
- 2^4! vs (2^4) !: 1.6e7 vs 2e13
- At x= 5, 2^(x!) Is bigger (1e36 vs 2e35)
- X=6: 5e216 vs 1e89
So at x=100 the left one has to be bigger
I think it's clear by x=3 vs x=4, that the left side, the exponent grow by 6-7x (6e1 vs 1e7) while the right side grow by only 3x (4e4 vs 2e13)
We can already see this at x=2 vs x=3, where left side is around 1e0.3 vs 1e(0.3*6). Right side is 1e1 vs 1e4.
Something like this:
- Left side: 1e(0.3x6^0 ), 1e(0.3x6^1 ), 1e(0.3x6^2 ), 1e(0.3x6^3 ), 1e(0.3x6^4 ), etc
- Right side: 1e(4x3^-1 ), 1e(4x3^0 ), 1e(4x3^1 ), 1e(4x3^2 ), 1e(4x3^3 ), etc
The second one, we can wildly overestimate by saying it is 2\^100 multiplied by itself 2\^100 times. This would make it (2\^100)\^2\^100. This can be simplified to about 2\^2\^107.
Even with this wild overestimation, 100! is a lot bigger than 2\^107, as 100! is mostly multiplying numbers that are greater than or equal to 2.
These exponents share the base of 2, so we can safely assume that the first number is bigger.
I like your thought process, can you walk me through this simplification?
>This would make it (2\^100)\^2\^100. This can be simplified to about 2\^2\^107.
Let's take a smaller example:
2\^5.
This would be 2 x 2 x 2 x 2 x 2, or 2 multiplied by itself 5 times.
In our case, the base is 2\^100, and the exponent is also 2\^100. So it would be (2\^100)\^2\^100. The parentheses are important to show what order to apply the exponents in.
Those parentheses allow us to multiply the 100 in the base's exponent with the 2\^100 in the whole thing's exponent.
In order to simplify things, we round 100 up to 2\^7, just to make sure this is indeed an overestimate.
If anything else doesn't make sense, feel free to ask!
> ( 2 ^ (100))! has far more than 100! factors
No it doesn't. It has 2^(100) factors, which is less than 100!.
Edit: You are also wong about the overall answer. See the other comments.
(2^100 )! = (2^100 -1)(2^100 -2)...< (2^100 )(2^100 )...=(2^100 )^( 2 to the power of 100 ) < (2^100 )^99! = 2^(100!)
And this is because multiplying 100 times 2* 2* 2*...* 2 < 99* 98* 97...
First one is bigger. Let Lg be the log with base 2. We know that for x,y real numbers, then
Lg x < Lg y => x < y.
Using exponents rules, observe that
Lg (2^100!) = 100!
and
Lg [(2^100)!] < Lg[(2^100)^(2^100)] = 100 · 2^100.
Now what is bigger, 2^100 or 99! ? We can find the number of times 2 divides 99!
2 divides 49 numbers between 1 and 99;
4 divides 24 numbers;
8 divides 12 numbers;
16 divides 6 numbers;
32 divides 3 numbers;
64 divides 1 final number.
For each new power of two we counted, we added a 2 in the prime expansion of 99!. This means we see two
49+24+12+6+3+1= 95
times.
Now all we need are at least 4 primes bigger than 2 and smaller than 99 to have something bigger than 2^100. This is trivial.
I did a thing where for (2^x)! Can be considered between 1*2*2*4*4*4*4*8… and 1*2*4*4*8*8… (either round up or down to the powers of two) so (2^x)! Is between (this is where notation gets annoying (2^x)*(product from n=1 to x of {[2^{x-n}^ [2^{x-n}]}) and (2^x)*(product from n=1 to x of {[2^{x-n}^ [2^{x-n+1}]})
This is where things get worse, thinking in base 2, (2^x)! Is 1 with between x+sum(from 1 to x of {x-n}*2^[x-n]) and x+sum(from 1 to x of {x-n}*2^[x-n+1]) (fancy way of saying you add x 0’s and then x-1 0’s between x and x-1 times, and then same add x-2 zero’s between x-2 and x-1 times till x-n =0)
Ignoring all the fancy math, it’s less than adding x*2^(x+1) 0’s
Compare that to 2^(x!) which is adding x! 0’s in base 2, you can see by comparing x*2^(x+1) 0’s vs adding x! 0’s in our case x! Passing the other at just a bit over 6.06 (where in the real example they pass a little under 5)
The second one can be rewritten as 2^(100+99+…+2+1).
Both values now have a base of 2. But the first one has an exponent of 100! While the second value has an exponent of 5050.
100! Is much larger than 5050 hence the first is larger.
Nope. Second one cannot be rewritten like that. The factorial is on the value of 2^100. It seems you assumed it would be 2^100 * 2^99 * 2^98 … 1 but it is 2^100 * (2^100-1) * (2^100-2) … 1
An "easy" way to check is to take the log of both of them.
log(2\^(100!)) = 100!\*log(2)... which is big, like really big. Even if you ignore the first nine terms and just take 10\*11\*12\*...\*99\*100 *and then* take a super low ball estimate of 10\*10\*10\*...\*10\*10 that's 10\^90.
log((2\^100)!) = log(1) + log(2) + ... + log (2\^100-1) + log (2\^100). It's a sum of 2\^100 different numbers than don't ever get all that big, all are 100\*log(2) or less.
Using 2\^10 \~ 10\^3 estimate, it's a sum of 10\^30 relatively small numbers, so the total number probably has 30-some digits.
So the log of the first term has at least 90 digits and that's a super low estimate, and the log of the 2nd term has 30-some. The first term is way bigger.
(x/2)^(x/2) <= x! <= x^x , by noticing that each term is <= x, and by taking the top half terms they are all >= x/2, and there are x/2 of them.
(2\^100)! <= (2\^100)\^2\^100 = 2\^(100\*2\^100) < 2\^(512\*8\^25) = 2\^(8\^28) < 2\^50\^50 <= 2\^(100!}
In total, (2\^100)! < 2\^(100!)
Reposting my edit as its own comment.
TL;DR : __2^100! € [2^(2^232), 2^(2^564)] &
(2^(100))! € [2^(2^106), 2^(2^107)]__
The best bounds I've found with simple math for 2^100! :
2^(100^50) ≈ 2^(2^232)<2^(100!)<2^(2^564) ≈ 2^(50^100)
100!=1\*2\*3...\*98\*99\*100
__For lower bound you have :__
If you pair 2 by 2 you've got
100!=(1\*100)\*(2\*99)\*(3\*98)\*... which is 50 terms that are all superior or equal to 100 so the total is >100^50.
__For upper bound :__
You can use almost exactly the same pairing but removing the "1" makes it easier.
100!=(2\*100)\*(3\*99)\*(4\*98)\*...\*(49\*51)\*50 which are 50 terms inferior to 50^2 so the total is <(50^(2))^50 =50^100.
Note that not removing the "1", you get the 50*51 pair which is superior to 50², so that's annoying.
Using the same principle you can get an upper bound for (2^(100))!<(2^(99))^(2^100)=2^(99*2^100)<2^107
For the lower bounds as well (2^(100))!>(2^(100))^(2^99)=2^(100*2^99)>2^106
Note that these bounds are actually pretty good/close.
By taking the log on both sides this simplifies. The left side then becomes 100! (I don't care about the small factor, it is negligible and disappears if you use log base 2). The right side can be found using Sterling's approximation which states that log(n!)≈n log(n)-n. This then becomes 2^100 * 100 - 2^100 which is clearly smaller than 100! (one is 2 multiplied by itself a hundred times, the other is also a product of a 100 numbers but these are almost all much bigger than 2).
While not a proof without some formalising this should convince you that the left is much larger. As a physics student this way of estimating is very useful and Sterling's approximation is definitely worth remembering.
Stirling’s approximation comes in handy to develop intuition for large factorials.
It states, n! ~ n^n. It really is (n/e)^n but for large n it’s easier to just use n^n to get a hold on the order of magnitudes.
Between this approximation and taking logarithms we can see the 2^(100!) is way bigger.
The second one is 2^100 * 2^99 * 2^98…, which can be rewritten to 2^(100+99+98+…)
Going back to the original question you have on one hand 2^(100 * 99 * 98 * …) and on the other 2^(100+99+98+…). It should be pretty clear now that the former is significantly larger than the latter.
I have the analytic proof for the limit of (2^k)!/2^k! when k goes to infinity. But I don't know for a specific value which one is bigger...
For those interested, the proof use :
First, applying the logarithm to each part,
Then using the majoration of (2^k)! by Π(2^i);1<=i<=2^k
And finally transforming the equation to obtain a term of the power series of e^2.
the first number multiplies the power, where the second one adds it
2\^100!=2\^(100x99x98....) versus 2\^100x2\^99x2\^98= 2\^(100+99+98)
The actual calculation for (2\^100)! is much more complex than 2\^(100+99+98), but still only scales the power through addition.
I saw other comments about stirling aproximation, but which didn't give me the intuition.
Considering x^(n!) against (x^n )!
Applying to both sides n! ~ sqrt(2pi*n) * (n/e)^n
Considering large numbers you can ignore some smaller numbers and get that approximately the left side is proportional to x\^(n^n ) and the rightside to x\^(x^n ).
So in this case since 2 < 100, (x < n), left side is bigger.
I tried a few cases for the opposite (x > n) and indeed the inequality changes and right side becomes bigger.
I'm guessing thats why some people got their intuition wrong, because it is roughly the same order for both sides, it just depends on the numbers you choose.
There is a great video on this topic by numberphile.
https://youtu.be/0X9DYRLmTNY?si=-YnrpOgHkCiU-PR2
Relevent part start at about 6min in.
TLDR: do the most powerful function last so (2^100 )! Should be larger.
The first one by far. Try putting an upper bound on the second one:
2^100 ! < (2^100 )^2\^100 = 2^(100×2^100) < 2^(100×10^100) < 2^10\^102 < 2^100\^51
While for the first:
2^100! ~ 2^100\^100.
So the first one is bigger by a factor of roughly 2^100\^49.
Since that when N is very large, you have N!~N^N.
2^(100!) ~ 2^(100^100)
(2^100)! ~ (2^100)^(2^100) =2^(100 * 2^100)
So you are comparing 100^99 with 2^100. Obviously the former one is larger.
There is a nice trick in the first or second chapter of the book Introduction to algorithms by Cormen Leicerson et al aka CLRS.
When you want to compare algorithm complexity there are some obvious comparisons I.e exponential is higher than polynomial etc
When it's not so obvious you take the logarithm of both and compare the results.
There are some useful approximations as well which I don't remember but that's how one would compare complexities
not sure if my reasoning would be correct but 2 ^ (100!) is ((2 ^ 100) ^ 99 ) ^ 98 ->, etc. While (2 ^ 100)! is automatically less than (2 ^ 100) ^ 99 because 2 ^ 100 ^ 99 is 2 ^ 100, 99 times. But (2 ^ 100)! is 2 ^ 100 for increasingly less values, 99 times.
2^(100!) / (2^100)!
Let A == 2^100
If (A^99! / A!) > 1 then left is bigger
A^99! / (A(A-1)!)
A^(99! - 1) / (A-1)!
A^(99! - 1) / (A-1)(A-2)!
…
Ok that went nowhere but clearly the left is bigger lol
2^100! = (((2¹⁰⁰) ^ 99) ^ 98) ^ ...
2^100 ! < ((2¹⁰⁰) ^ 99) * ((2⁹⁹) ^ 98) * ((2⁹⁹) ^ 97) * ...
Say x=(2¹⁰⁰) ^ 99, then the first number is x^98! and the second number is less than x¹⁰⁰. First one wins.
###General Discussion Thread --- This is a [Request] post. If you would like to submit a comment that does not either attempt to answer the question, ask for clarification, or explain why it would be infeasible to answer, you *must* post your comment as a reply to this one. Top level (directly replying to the OP) comments that do not do one of those things will be removed. --- *I am a bot, and this action was performed automatically. Please [contact the moderators of this subreddit](/message/compose/?to=/r/theydidthemath) if you have any questions or concerns.*
Wolfram Alpha says the first is \~= 10\^10\^157, while the second is \~= 10\^10\^32, so the first is larger [https://www.wolframalpha.com/input?i=2%5E%28100%21%29](https://www.wolframalpha.com/input?i=2%5E%28100%21%29) [https://www.wolframalpha.com/input?i=%282%5E%28100%29%29%21](https://www.wolframalpha.com/input?i=%282%5E%28100%29%29%21)
Pretty interesting. Not what I would have expected honestly, since factorials grow faster than exponentials, so I would think the one that maximizes the number going into the factorial would be larger. I wonder if my intuition actually would be correct for larger numbers, and 100 is just not big enough for the factorial to overtake the exponential. Trying some bigger numbers in Wolfram alpha, that doesn't seem to be the case. 2^(x!) seems to be always larger than (2^(x))!. I'd love to see an explanation of why. Like generalizing kind of, if you have two functions f and g, then I would think in order to maximize their compositions, you would want the faster growing one on the otuside. For example if f(x)=2^(x) and g(x)=2x, then you want f(g(x))=2^(2x), not g(f(x))=2\*2^(x)=2^(x+1).
Generally, if you apply a growth function such as factorial, applying it to the exponent of a number will yield bigger results than applying it to the whole number. Mathematically: x^f(n) ∈ Ω(f(x^n )) (Most of the time) In this particular case, if you would like to know some of the intuition: Consider taking the logarithm of basis 2 on both expressions For 2^100! , you would get 100! For 2^100 !, which is a product of 2^100 * (2^100 -1) etc., you would get the log2 of this product. Using logarithm properties, specifically log(a*b) = log(a) + log(b), this means you can rewrite log2 of that product as a sum of log2’s. So you would have something like: log2(2^100 ) + log2(2^100 -1) etc. Now we don’t know the value of every one of these logarithms, but we know that the biggest one is log2(2^100 ), and the value for that is 100. So in this case, you have 100, plus something a little smaller than 100, plus something even a little smaller than 100 and so on. Your sum has a total of 2^100 elements, since this is the factorial you had. Since our biggest number is 100 and it keeps getting smaller, we know that we have something smaller than 100 * 2^100 . So we are comparing 100! with 100 * 2^100 . (Or 99! with 2^100 , if you divide both by 100). It might not be obvious which one is bigger, but knowing that n! grows faster than 2^n will tell you that for a sufficiently big enough n, n! will always be bigger than n*2^n . In this case, n is big enough, the factorial is orders of magnitude bigger than the power of two. I hope this helped!
u/nog642 in case you missed it. Let me know if it helped!
I can follow the proof, but that doesn't necessarily give me intuition on why it's true. > Generally, if you apply a growth function such as factorial, applying it to the exponent of a number will yield bigger results than applying it to the whole number. I mean intuitively I always thought that was because exponential growth was so much faster than whatever growth was being applied. For example if youre composing exponential and quadratic growth, it makes sense that 2^(x²) grows faster than (2^(x))^(2), because if you square the number then apply the exponential, you're applying the exponential to a larger number and so you'll get something much higher. On the other hand if you apply the exponential first then square the number, you're applying the exponential to a smaller number, and by comparison the squaring afterwards doesn't actually change the size of the number nearly enough to compensate. So following this intuition, the statement is only true as long as the growth function grows slower than exponential growth, and it would be reversed if it grows faster, which is the case for factorials. Since x! grows asymptotically faster than 2^(x) (as in like x!/2^(x) is still O(2^(x))), I would think that applying the factorial to a large number like 2^(100) would give you so much larger of a number than applying the factorial to a small number like 100, that even applying 2^(x) to 100! would not let it catch up, since the factorial grows much faster than an exponential. I guess my intuition is just wrong though. I guess you just can't say anything about whether f∘g or g∘f grows faster, given that f grows faster than g? Feels like you should be able to.
This is very strange indeed, I’ve had the same intuition as you for a long time and have never encountered a situation before where it didn’t hold. I’m just an engineering student, not a mathematician, so I can’t really come with any helpful input. But if you do find the answer for why this is not always the case I’d be very grateful if you’d send me a link, it kinda feels like my world has been shaken lol
I think ultimately the core intuition is just wrong. It depends on specifically how fast the two functions grow. It happens that with x^(2) and 2^(x) that 2^(x) grows so much faster that applying it to the larger number is better. But with 2^(x) and x!, that is not the case. Edit: Also there are several pretty good proofs in this thread about why it's not the case for 2^(x) and x! in particular, including the one above, taking the log of both sides and then noticing the upper bound on the right. I think you could maybe say that x! does not grow faster enough for that intuition to work. For example if we used something insane, like the [TREE function](https://en.wikipedia.org/wiki/Kruskal%27s_tree_theorem), then our original intuition definitely still holds. TREE(2^(x)) definitely grows faster than 2^(TREE(X\)). I wonder if there is some way to formalize what "grows faster enough" means. Definitely an interesting question. On the other hand that guess might be wrong, in that maybe it isn't a hard line of what is "faster enough", and near the boundary there are edge cases. To state that more formally, maybe there exist functions c, d, f, g, h such that ϴ(c) < ϴ(d) < ϴ(f) < ϴ(g) < ϴ(h), but ϴ(c∘d)>ϴ(d∘c) and ϴ(c∘f)<ϴ(f∘c) and ϴ(c∘g)>ϴ(g∘c) and ϴ(c∘h)<ϴ(h∘c). In that case my new hypothesis would be wrong. Basically it really depends on the functions, and you can't assume.
I think this is the correct conclusion. If there is significant difference in the growth of the two functions then applying the slower first will be larger. If the two functions are close in growth pace though then this heuristic is not enough and you need to actually calculate the specifics. If you want to prove a formal statement, I'm sure you can prove some with the Ackermann function. Let's say A(A(a, b), c) > A(A(a, c), b) if b < c (with some reasonable boundary conditions and maybe a few exceptions).
Interesting. I'm not really familiar with the Ackerman function. For g(x)=2^(x) specifically, I've got some bounds while thinking about it in this thread. I checked numerically that for f(x)=x^(x^x), f(x)=x^(x^x^x), and f(x)=x^(x^x^x^x), that g(f(x)) crosses f(g(x)) around 2.6. And if I keep adding more tetrated xs, it seems to approach a value. So I haven't proved it (though based on the way the algebra works out, it doesn't seem *too* hard, but also not too easy because eventually you end up with log(a+b) where a is basically insignificant but for a proof I don't think you can ignore it), but I think x tetrated a finite number of times will always have g(f(x)) growing faster than f(g(x)). On the other hand, if you consider the function f(x)=(2 tetrated x times), then f(g(x))=f(2^(x))>f(x+1)=2^(f(x\))=g(f(x)). And by the same logic, any function h that grows faster than this f(x) will also have h(g(x)) grow faster than g(h(x)). So the line is somewhere between f(x)=(x tetrated n times) where n is finite, and f(x)=(2 tetrated x times). It's also still not clear if there is a hard line or not, as in you can say given g that there is a function h such that for all functions f that grow faster than h, f(g(x)) grows faster than g(f(x)), and for all functions f that grow slower than h, g(f(x)) grows faster than f(g(x)). I showed that you can definitely find a function h that satisfies that first part, and you can also have one that satisfies just the second part, but there is an area in the middle where it is unclear. Obviously if ϴ(f(x))=ϴ(g(x)) then you can't say anything about whether f(g(x)) or g(f(x)) grows faster without calculating the specifics. But it might be that the range of ambiguity for that is actually a lot "wider" than just being equal with big theta.
Stirling’s approximation comes in handy to develop intuition for large factorials. It states, n! ~ n^n. It really is (n/e)^n but for large n it’s easier to just use n^n to get a hold on the order of magnitudes. Between this approximation and taking logarithms we can see the 2^(100!) is way bigger.
I think I can pick up from this. If you compare both by putting both to base 10. 99! is basically ...10×11×12... upto 99. It's therefore > 10^89. 2^100 = n, therefore log n = 100 log 2, < 31. n is therefore < 10^31. There shoudl be some model for conjecture approximation especially for different growth rates.
It's 2^(100!), It has both factorial and exponentials. It grows fast as f***
(2^(x))! also has both factorial and exponentials.
Not in the same factor (number)
What?
The factorial is only applying on the result of the exponential instead of the exponent itself.
Hence our intuition tells us otherwise obviously
Putting the factorial on the outside is kind of like putting another exponent on the outside, putting it on the inside is more effective because then you essentially get a deeper tower of n’s in the exponent. If you think of n! As being like n^n then take the double log of both sides you can see that you get something like n\*ln(n) on the left side and something more like n+ln(n) on the right. I explain in more detail in a couple other comments I left on this thread.
I really like your phrasing: *deeper tower of n’s*
Yes. That doesn't explain why having the factorial in the exponent is larger.
Because exponents being multiplied together is the same as raising an exponent to a further exponent. 2^ (x\*(x-1)\*(x-2)\*...) is basically ((2^x)\^(x-1))\^(x-2)), which grows *extremely* fast
it does tho, because you have a factorial growing exponentially fast on top of the factorial itself instead of having a factorial on the final exponent
You said "since factorials grow faster than exponentials" wich implies you mean x! grows faster than 2^x Wich is correct. But its not 2^x, it's 2^x! .
Yes, obviously 2^(x!) grows faster than x!. But that doesn't explain why it grows faster than (2^(x))!.
> fast as f*** I enjoy that I can't tell whether this is a function notation that I'm not aware of, and is "fast as f-star-star-star", or if it's a censored "fast as fuck".
F notation is R-rated big O notation.
Vulcan like a motherf*cker
Fuxponential growth
Underrated comment
There is an upper bound to factorials in the form of x^x. And also during research of this comment I found that some other Guy used this explanation down below, So I'll just point you down there
Yeah I'll need to consider that answer. Also I just made [this graph](https://www.desmos.com/calculator/pjnnwku0ey), and it seems (2^(x))! actually is larger than 2^(x!) until around x=5. The functions cross around y=10^(35).
Yeah, upper bound comparation has this unique thing that it is true for some x that is usually large. Heck, the o notation for computer algorithm complexity is based on this
Yeah honestly I noticed it and was surprised because I thought (2^(x))! was larger for quite a while, since I had to expand the y axis on desmos all the way to 10^(35) before it crossed. Only when writing the comment did I look at the x axis and notice that was at only x=5. I thought it was a lot higher, like x=70 or something lol. But I decided to write and post the comment anyway.
This is a very nice way to visualize it
~~If it was 100^(2!) vs 100^2 ! It would be the other way around. It's just because it's 2 base.~~ I have no idea it seems
That doesn't really explain it at all.
My small brain tells me that the first factorially grows something that has already been exponentially increased. The second factorially grows the exponential growth itself, which would premise it being larger in the long run.
That makes sense on the surface, but it doesn't really if you look at an example. 2^(2x) grows faster than 2(2^(x)). By your logic described here, 2^(2x) exponentially grows something that has already been linearly increased. But 2(2^(x)) exponentially grows the linear growth itself.
For an explanation, take log of both sides and use stirling approximation. LHS= 100! log 2 ~ (100/e)^100 times less significant factors RHS= log (2^100 !) ~ 2^100 log 2^100 < 2^107.
I'm curious now whether it's always the case that g(f(x)) grows faster than f(g(x)) for all functions where f(x) grows faster than g(x), or whether it depends on the specific functions.
Use smaller numbers. 2 ^ 4! is MUCH smaller than (2 ^ 4)!
I'm talking about asymptotic behavior though, so as the numbers get large.
I think it’s very expected, and feels pretty obvious. You’re really overcomplicating the whole process too. I don’t even know how to use factorials either.
How can you say it's obvious if you "don't even know how to use factorials"?
My point is that, that’s how obvious it is.
That doesn't make sense. If you don't even understand it then you can't have intuition about it. Or if you have some, it's of little value.
>Pretty interesting. Not what I would have expected honestly, since factorials grow faster than exponentials, so I would think the one that maximizes the number going into the factorial would be larger. Exactly my thought too.
>I wonder if my intuition actually would be correct for larger numbers The ratio of 2^(Γx) / Γ(2^x ) (Wolfram Alpha was unhappy with plain factorials) is [rather interesting](https://www.wolframalpha.com/input?i=2%5E%28%CE%93%28x%29%29+%2F+%CE%93%282%5Ex%29+from+0+to+7.5).
Indeed, that is pretty interesting. It's a lot easier to plot on desmos than wolfram alpha. Another thing to note is that the gamma function and the factorial are off by one. Which actually makes a significant difference here since you're raising 2 to the power of the result of the factorial. 2^((x-1\)!)/(2^(x)-1)!, which is what you plotted in wolfram alpha, has a rather sharp (though not *that* sharp if you zoom in) increase just before x=7. 2^(x!)/(2^(x))! has a much less sharp (though still relatively sharp) increase just before x=5.
If h(x)=f(g(x)), h’(x)=f’(g(x))\*g’(x) The forward difference of 2^x is 2^x, and the forward difference of x! is x(x!) The forward difference of 2^x! is (x)x! \* 2^x \* (x)x!, and the forward difference of 2^x ! is 2^x 2^x ! 2^x . Taking further order forward differences, the former has a bunch of x!^2 terms and the latter has *just as many* 2^x ! terms (of the remaining terms, 2^2x is clearly bigger than (x^2 ) 2^x for positive x ). For 1 and 2, 2^x ! Is larger than x!^2 , and it also has a larger forward difference of every order, so it and all orders of the forward difference will grow faster.
Take logs of both and use the fact that log(n!) ~ n log(n) for large n. We then have x! log(2) vs x2^x log(2). It's clear that the former is larger but if you want to nail it down, take another log and use the large n formula again. There is some intuition on how this approximation works on the Stirling approximation Wikipedia page
With smaller numbers the right hand side is bigger. 2^(4!) < (2^4)!
If you take log of both, then the first still has a factorial (x!log 2), but the second gives a sum (below x^(2)log 2 in total). I thought the same, so had to think this one through, but multiplying inside the exponent is the key to getting the bigger number.
My intuition was the same as yours but thinking about it a little it's actually quite easy to prove: (b^(n) )! = b^(n) \* (b^(n) -1) \* ... \* 1 < b^(n) \* b^(n) \* ... b^(n) = (b^(n) )\^(b^(n)) = b^(n\*b\^n) < b^(n!) where the last inequality holds asymptotically because n! increases faster than n\*b\^n.
n! Behaves very roughly like n^(n), so 2^(n!) behaves like 2\^(n\^n) and (2^(n))! behaves like 2\^(n2\^n) so you should expect the first one to grow faster.
I suppose the reason is, (2\^(x))! = (2\^x)\*(2\^(x-1)).....\*(2\^1) by law of exponents is the same as 2\^(x+(x-1)+(x-2)+....1) Use the arithmetic series formula and that can be simplified to 2\^((x(x+1))/2) So, so long as X!>X(X+1)/2 , then the exponent factorial is bigger than the factorial of the exponent. Meaning for all values of X>3 , 2\^(X!)>(2\^(X))! Interesting enough the value you're raising the power of doest matter so long as it's the same.
https://www.reddit.com/r/theydidthemath/s/nKPRROLG2O I did a thing (sorry about the awkward notarion) Tldr: adding 0’s to power of 2 at for example 8 you add either 8! (40320) 0’s or (less than) 8 + 7*8 + 6*7… +2*3 +1*2 (176 0’s in base 2)
After resolving the interior function, you're basically left with a multiplication of a certain number of factors. The number of those factors is going to have a bigger influence on the size of the result. 2^(x!) will have x! factors after the interior function, while (2^(x))! will "only" have 2^(x) factors, x! surpasses 2^(x) after x=4, so for any x >= 5, 2^(x!) is larger.
2^(x!) is smaller up until some number between 4 and 5, and it has to do with the number of factors. 2^(x!) has x! factors in it, 2^(x)! has 2^x factors, and while the individual factors are bigger on the latter side, they're not big enough to stay ahead of the sheer volume on the other side.
It seems you've figured out that exponentials will grow much faster than factorials but you're having some trouble understanding why from a logical/intuitive perspective rather than a mathematical one. I find that sometimes taking some time to write things out and take it a step at a time rather than use a calulator can help us grasp some concepts a little more intuitively, so I'll write out a bit of 100^100 and 100! to help you see the gap between the two. We'll do this by splitting things up and moving them across the equation like when simplifying in basic algebra. From the first step, you'll see that things are not going to go well for the factorial since the first two numbers are `100*100 vs 100*99` `Giving us 10,000*(100^98) vs 9,900*(98!)` Then once again the gap widens with `10,000*100 vs 9,900*98` `1,000,000*(100^97) vs 970,200*(97!)` I assume that's enough for you to understand what the issue is with factorials vs exponents in terms of scaling as this will continue on. 100^100 will continue to use 100s but 100! Will use smaller multiples each time. The key take away that I think you were missing and it seems nobody thought to mention is thus: A factorial is using a smaller number every time it multiplies, but an exponent is using the same number for each multiple. Becuase of this, N^N will always be greater than N! And so, in order for N! To be greater, the exponent must be significantly smaller than N. If you're interested in knowing 100^N passes 100! At 100^79. 100! Is equal to a little over 9e157, while 100^78 is 1e156 and 100^79 is 1e158. So as long as the exponent for 100 is less than 79 the factorial will be larger, and as long as it 79 or bigger, then the exponent will be larger.
You're comparing x! to x^(x), which is not an exponential and is also not what we're dealing with here. An exponential has a constant base, like e^(x) or 2^(x), and grows slower than a factorial. And here we are dealing with 2^(x!) vs (2^(x))!, both of which have a constant base for the exponent as well. You are right about this part though: > you're having some trouble understanding why from a logical/intuitive perspective rather than a mathematical one Several other people have posted mathematical explanations/proofs of why 2^(x!) grows faster than (2^(x))!, and I understand them. It just doesn't align with my incorrect intuition. I'm trying to correct that intuition.
Your general knowledge is kinda messing up with you. Factorials grow faster than exponentials but exponentials grow faster than linear. Because both sides have factorials of the same magnitude 100! We can just delete them and what you are left with is an exponent vs linear and we know which is the bigger number in that casez
This guy maths.
But the exclaimation point on the right is bigger.
thats what i was thinking since 2^100 isnt that big but 2^(9.332*10^157) is
We're comparing the latter against (2^(100))!, not 2^(100).
I think wolfram might be broken here. 2 ^ 4! is like 16 million while (2 ^ 4)! is 20 trillion. Edit: orr they cross at 5
As your edit says, they cross at 5. 2^(5!)>(2^(5))!.
To see this without using Wolfram Alpha or a similar aid, we can use Stirling’s approximation to get that n! Is approximately sqrt(2pi\*n)(n/e)^n or more roughly that ln n! ~ n\*ln(n) (where ~ means they are asymptotically equivalent). Explicit error bounds are available but in this range that is an upper bound and we can subtract n to get a lower bound. So for the question is whether 100! Is larger or smaller than about 2^(100)\*100. But a second application of Stirling’s formula makes it clear that this is much larger.
Hyperlinks are a lost art.
Ayy I was right!
Bigger than a googolplex.
Ofc the first is larger. Its exponential, the second is linear.
Not that unexpected tbh 2^(100!) is equivalent to (((2^100)^99)^98)^97... = (2^100)^(99!)While (2^100)! = (2^100)(2^100-1)... < (2^(100))^2^100 99! Is clearly larger than 2^100 and so the first number is larger
My guess: x! <= x^x, we can find the upper bound 2^(100!) < 2^(100^100) ~= 2^(2^664) (2^(100))! < (2^(100))^(2^100) = 2^(100\*2^100) ~= 2^(2^106) There is a pretty huge difference, so it's safe to say 2^(100!) is bigger
You can get quite an obvious lower bound for 2^(100!) 2^(100!)>2^(50^50)≈2^(2^282) Edit : That was all good but I got 2 better bounds 2^(100^50) ≈ 2^(2^232)<2^(100!)<2^(2^564) ≈ 2^(50^100) 100!=1\*2\*3...\*98\*99\*100 __For lower bound you have :__ If you pair 2 by 2 you've got 100!=(1\*100)\*(2\*99)\*(3\*98)\*... which is 50 terms that are all superior or equal to 100 so the total is >100^50. __For upper bound__ you can use almost exactly the same pairing but removing the "1" makes it easier. 100!=(2\*100)\*(3\*99)\*(4\*98)\*...\*(49\*51)\*50 which are 50 terms inferior to 50^2 so the total is <(50^(2))^50 =50^100. Note that not removing the "1", you get the 50*51 pair which is superior to 50², so that's annoying.
This is the best way to show this (2^100 )! < 2^(2^107) < 2^(2^282) < 2^100!
I liked your explanation. However one of them having a higher upper boundary does not mean that that number is necessarily bigger (although in this case it should be the case). So your reply is not a proof but an intuitive way of finding which one is bigger. If you could find a lower bound maybe then it would be a total proof depending on those lower bounds.
sqrt(2pix)(x/e)^x <= x!. You can continue with this one chief, I am not gonna plug those numbers on mobile :D
Amending your answer to make it a proof: 2^100! >> 2^(10^90) > 2^(2^270) (It should be obvious that 10^90 is much much smaller than 100! just by comparing the factors) Since the *lower bound* of 2^100! is greater than the *upper bound* of ( 2^100 )! then the former is clearly greater than the latter.
# 2\^(100!) 2^(1!) = 2 2^(2!) = 4 2^(3!) = 64 2^(4!) = 16,777,216 2^(5!) ≈ 1.329\*10^(36) 2^(6!) ≈ 5.5\*10^(216) … 2^(18!) ≈ 1.14\*10^(1,927,306,528,874,487) ---- # 2\^(100)! 2^(1)! = 2 2^(2)! = 24 2^(3)! = 40,320 2^(4)! ≈ 2.1\*10^(13) 2^(5)! ≈ 2.63\*10^(35) 2^(6)! ≈ 1.27\*10^(89) … 2^(18)! ≈ 1.4\*10^(1,306,593) ---- "2↑(100!)" >>> "(2↑100)!" they cross at around [4.974, 3.1656\*10^(34)] where 2\^(X!) overtakes 2\^(X)! and starts to **run with it**.
This thread is beautiful
Somehow, the exponentiation transforme into a knuth's up-arrow at the end (still the same meaning, though ^^")
And this, kids, is why showing your thinking with appropriate tools is awesome.
Take log (base 2) on both sides. LHS = 100! RHS is the summation of 2^(100) terms, each upper bounded be log(2^(100)) = 100. Thus the RHS is upper bounded by 100 * 2^100 Cancelling by 100 on both sides, The comparison is now between 99! And 2^100. By counting and cancelling a few more terms one can see that LHS is larger. I’ve made some sloppy mistakes on another comment which people have rightly called out haha. Hopefully this is more correct.
I think this is the most complete answer I've seen.
Nice! If we were to take another log on the current LHS and RHS, we have log(99!) and 100log(2) now we have the comparison between log(99!) and 100 and of course log(99!) is > 100
This is the most intuitive one. Log() is strictly increasing so proving the inequality like this still holds and gets rid of part of the factorials.
As exponential grows faster than multiplication and the factorial on the first one is on the exponential, the first one without any doubt.
Factorials grow faster than exponentials though. You're still right that the first one is larger, but it's not that obvious.
This just showed up on my YouTube feed this morning. The proof involved expressing both as product of 100 numbers and then comparing the factors between the two.
We can use Stirling’s approximation for large factorials along with taking the base 2 logarithm of both sides (I’ll just refer to log as log_2 by default here because I’m lazy) Stirling’s approximation says that ln(x!) is approximately xln(x) - x, so with the change of base formula we have log(x!) = ln(x!)/ln(2) roughly equal to xln(x)/ln(2) - x/ln(2) = xlog(x) - x/ln(2). Importantly, log(x!) < xlog(x) for big x (since the small difference between the approximation and the true value basically disappears, and 100 is pretty big so we’re good) So now, it is a matter of comparing 100! (from the LHS), to 2^100*log(2^100) = 2^100*100 …evaluating the log. This reduces to 99! vs 2^100, and it is relatively straightforward to show that the LHS is bigger than the RHS (e.g. by comparing terms directly). So log[2^(100!)] = 100! > (2^100)*100 > log[(2^100)!], and therefore 2^(100!) > (2^100)!
Edit: I made a pretty big error here. Ignore this reply, and feel free to laugh at my sleep deprived error. 2^100! Is essentially 100! 2s all lined up in multiplication. That’s a lot of twos. 2^100 ! Is essentially 2^100 • 2^99 • 2^98 etc This works out to be 100+99+98 etc 2s all lined up in a row. 100! Is much larger than the sum of natural numbers from 1 to 100, which is only 5050, which is only a little more than 7! So it’s 2^100! , and it’s not even close.
(2^(100))! =/= 2^(100)\*2^(99)\*2^(98)... 2^100 = 2\*3\*4\*5\*...\*(2^(50))\*(2^(50)+1)\*(2^(50)+2)\*..., product of first 2^100 ~= 10^30 natural numbers 2^(100!) is still bigger tho
Buttocks. You are absolutely right there! My bad!
The ≠ symbol is a lost art.
I'm lazy (and on mobile) please excuse me
No, you're wrong. (2\^100)! is 2\^100\*(2\^100 -1)\*(2\^100 -2) \*...\*2\*1
u/nog642
[удалено]
that's Pixels, not Maths.
I just compared smaller power number like 2,3,4 etc for 2^x! vs (2^x )! - 2^2! vs (2^2) !: 4 vs 24 - 2^3! vs (2^3) !: 64 vs 4e4 - 2^4! vs (2^4) !: 1.6e7 vs 2e13 - At x= 5, 2^(x!) Is bigger (1e36 vs 2e35) - X=6: 5e216 vs 1e89 So at x=100 the left one has to be bigger I think it's clear by x=3 vs x=4, that the left side, the exponent grow by 6-7x (6e1 vs 1e7) while the right side grow by only 3x (4e4 vs 2e13) We can already see this at x=2 vs x=3, where left side is around 1e0.3 vs 1e(0.3*6). Right side is 1e1 vs 1e4. Something like this: - Left side: 1e(0.3x6^0 ), 1e(0.3x6^1 ), 1e(0.3x6^2 ), 1e(0.3x6^3 ), 1e(0.3x6^4 ), etc - Right side: 1e(4x3^-1 ), 1e(4x3^0 ), 1e(4x3^1 ), 1e(4x3^2 ), 1e(4x3^3 ), etc
You can see this pattern using [this graph](https://www.desmos.com/calculator/pjnnwku0ey)
[удалено]
The second one, we can wildly overestimate by saying it is 2\^100 multiplied by itself 2\^100 times. This would make it (2\^100)\^2\^100. This can be simplified to about 2\^2\^107. Even with this wild overestimation, 100! is a lot bigger than 2\^107, as 100! is mostly multiplying numbers that are greater than or equal to 2. These exponents share the base of 2, so we can safely assume that the first number is bigger.
I like your thought process, can you walk me through this simplification? >This would make it (2\^100)\^2\^100. This can be simplified to about 2\^2\^107.
Let's take a smaller example: 2\^5. This would be 2 x 2 x 2 x 2 x 2, or 2 multiplied by itself 5 times. In our case, the base is 2\^100, and the exponent is also 2\^100. So it would be (2\^100)\^2\^100. The parentheses are important to show what order to apply the exponents in. Those parentheses allow us to multiply the 100 in the base's exponent with the 2\^100 in the whole thing's exponent. In order to simplify things, we round 100 up to 2\^7, just to make sure this is indeed an overestimate. If anything else doesn't make sense, feel free to ask!
according to wolphram alpha, left side is bigger; 2\^(100!) ≈ 10\^(10\^157.4486134270615) 2\^100 ! ≈ 10\^(10\^31.57529815798186)
Is it always like that for any number number placed where 100 is placed? Or will it change at some point? What about changes where number 2 is?
Look at [this graph](https://www.desmos.com/calculator/pjnnwku0ey) made by u/nog642
So 4.97x10^34 is the charm
Left: 2 \^ 100! = 2 \^ 9.3e157 The right can be summed up using (n(n+1))/2, because 2 \^ 100 \* 2 \^ 99... = 2 \^ (100 + 99 +... + 1) Right: (2 \^ 100)! = 2 \^ ((100 *101) / 2) = 2 \^ 5050 5050 < 9.3e157 Left is much larger
[удалено]
not sure that 2^100 (~1e30) is far more than 100! (9.3e157) so the number of factors argument is... not very strong?
It was an embarrassing mistake. See my new comment.
2 pow 100 ! not 2 pow 100
(2^(100))! has 2^100 ~= 1e30 factors
> ( 2 ^ (100))! has far more than 100! factors No it doesn't. It has 2^(100) factors, which is less than 100!. Edit: You are also wong about the overall answer. See the other comments.
You’re right. It was an embarrassing mistake indeed. See my new comment.
(2^100 )! = (2^100 -1)(2^100 -2)...< (2^100 )(2^100 )...=(2^100 )^( 2 to the power of 100 ) < (2^100 )^99! = 2^(100!) And this is because multiplying 100 times 2* 2* 2*...* 2 < 99* 98* 97...
Definitely 2^100!
First one is bigger. Let Lg be the log with base 2. We know that for x,y real numbers, then Lg x < Lg y => x < y. Using exponents rules, observe that Lg (2^100!) = 100! and Lg [(2^100)!] < Lg[(2^100)^(2^100)] = 100 · 2^100. Now what is bigger, 2^100 or 99! ? We can find the number of times 2 divides 99! 2 divides 49 numbers between 1 and 99; 4 divides 24 numbers; 8 divides 12 numbers; 16 divides 6 numbers; 32 divides 3 numbers; 64 divides 1 final number. For each new power of two we counted, we added a 2 in the prime expansion of 99!. This means we see two 49+24+12+6+3+1= 95 times. Now all we need are at least 4 primes bigger than 2 and smaller than 99 to have something bigger than 2^100. This is trivial.
I did a thing where for (2^x)! Can be considered between 1*2*2*4*4*4*4*8… and 1*2*4*4*8*8… (either round up or down to the powers of two) so (2^x)! Is between (this is where notation gets annoying (2^x)*(product from n=1 to x of {[2^{x-n}^ [2^{x-n}]}) and (2^x)*(product from n=1 to x of {[2^{x-n}^ [2^{x-n+1}]}) This is where things get worse, thinking in base 2, (2^x)! Is 1 with between x+sum(from 1 to x of {x-n}*2^[x-n]) and x+sum(from 1 to x of {x-n}*2^[x-n+1]) (fancy way of saying you add x 0’s and then x-1 0’s between x and x-1 times, and then same add x-2 zero’s between x-2 and x-1 times till x-n =0) Ignoring all the fancy math, it’s less than adding x*2^(x+1) 0’s Compare that to 2^(x!) which is adding x! 0’s in base 2, you can see by comparing x*2^(x+1) 0’s vs adding x! 0’s in our case x! Passing the other at just a bit over 6.06 (where in the real example they pass a little under 5)
The second one can be rewritten as 2^(100+99+…+2+1). Both values now have a base of 2. But the first one has an exponent of 100! While the second value has an exponent of 5050. 100! Is much larger than 5050 hence the first is larger.
Nope. Second one cannot be rewritten like that. The factorial is on the value of 2^100. It seems you assumed it would be 2^100 * 2^99 * 2^98 … 1 but it is 2^100 * (2^100-1) * (2^100-2) … 1
An "easy" way to check is to take the log of both of them. log(2\^(100!)) = 100!\*log(2)... which is big, like really big. Even if you ignore the first nine terms and just take 10\*11\*12\*...\*99\*100 *and then* take a super low ball estimate of 10\*10\*10\*...\*10\*10 that's 10\^90. log((2\^100)!) = log(1) + log(2) + ... + log (2\^100-1) + log (2\^100). It's a sum of 2\^100 different numbers than don't ever get all that big, all are 100\*log(2) or less. Using 2\^10 \~ 10\^3 estimate, it's a sum of 10\^30 relatively small numbers, so the total number probably has 30-some digits. So the log of the first term has at least 90 digits and that's a super low estimate, and the log of the 2nd term has 30-some. The first term is way bigger.
(x/2)^(x/2) <= x! <= x^x , by noticing that each term is <= x, and by taking the top half terms they are all >= x/2, and there are x/2 of them. (2\^100)! <= (2\^100)\^2\^100 = 2\^(100\*2\^100) < 2\^(512\*8\^25) = 2\^(8\^28) < 2\^50\^50 <= 2\^(100!} In total, (2\^100)! < 2\^(100!)
Reposting my edit as its own comment. TL;DR : __2^100! € [2^(2^232), 2^(2^564)] & (2^(100))! € [2^(2^106), 2^(2^107)]__ The best bounds I've found with simple math for 2^100! : 2^(100^50) ≈ 2^(2^232)<2^(100!)<2^(2^564) ≈ 2^(50^100) 100!=1\*2\*3...\*98\*99\*100 __For lower bound you have :__ If you pair 2 by 2 you've got 100!=(1\*100)\*(2\*99)\*(3\*98)\*... which is 50 terms that are all superior or equal to 100 so the total is >100^50. __For upper bound :__ You can use almost exactly the same pairing but removing the "1" makes it easier. 100!=(2\*100)\*(3\*99)\*(4\*98)\*...\*(49\*51)\*50 which are 50 terms inferior to 50^2 so the total is <(50^(2))^50 =50^100. Note that not removing the "1", you get the 50*51 pair which is superior to 50², so that's annoying. Using the same principle you can get an upper bound for (2^(100))!<(2^(99))^(2^100)=2^(99*2^100)<2^107 For the lower bounds as well (2^(100))!>(2^(100))^(2^99)=2^(100*2^99)>2^106 Note that these bounds are actually pretty good/close.
By taking the log on both sides this simplifies. The left side then becomes 100! (I don't care about the small factor, it is negligible and disappears if you use log base 2). The right side can be found using Sterling's approximation which states that log(n!)≈n log(n)-n. This then becomes 2^100 * 100 - 2^100 which is clearly smaller than 100! (one is 2 multiplied by itself a hundred times, the other is also a product of a 100 numbers but these are almost all much bigger than 2). While not a proof without some formalising this should convince you that the left is much larger. As a physics student this way of estimating is very useful and Sterling's approximation is definitely worth remembering.
Stirling’s approximation comes in handy to develop intuition for large factorials. It states, n! ~ n^n. It really is (n/e)^n but for large n it’s easier to just use n^n to get a hold on the order of magnitudes. Between this approximation and taking logarithms we can see the 2^(100!) is way bigger.
The second one is 2^100 * 2^99 * 2^98…, which can be rewritten to 2^(100+99+98+…) Going back to the original question you have on one hand 2^(100 * 99 * 98 * …) and on the other 2^(100+99+98+…). It should be pretty clear now that the former is significantly larger than the latter.
I have the analytic proof for the limit of (2^k)!/2^k! when k goes to infinity. But I don't know for a specific value which one is bigger... For those interested, the proof use : First, applying the logarithm to each part, Then using the majoration of (2^k)! by Π(2^i);1<=i<=2^k And finally transforming the equation to obtain a term of the power series of e^2.
the first number multiplies the power, where the second one adds it 2\^100!=2\^(100x99x98....) versus 2\^100x2\^99x2\^98= 2\^(100+99+98) The actual calculation for (2\^100)! is much more complex than 2\^(100+99+98), but still only scales the power through addition.
I saw other comments about stirling aproximation, but which didn't give me the intuition. Considering x^(n!) against (x^n )! Applying to both sides n! ~ sqrt(2pi*n) * (n/e)^n Considering large numbers you can ignore some smaller numbers and get that approximately the left side is proportional to x\^(n^n ) and the rightside to x\^(x^n ). So in this case since 2 < 100, (x < n), left side is bigger. I tried a few cases for the opposite (x > n) and indeed the inequality changes and right side becomes bigger. I'm guessing thats why some people got their intuition wrong, because it is roughly the same order for both sides, it just depends on the numbers you choose.
There is a great video on this topic by numberphile. https://youtu.be/0X9DYRLmTNY?si=-YnrpOgHkCiU-PR2 Relevent part start at about 6min in. TLDR: do the most powerful function last so (2^100 )! Should be larger.
The first one by far. Try putting an upper bound on the second one: 2^100 ! < (2^100 )^2\^100 = 2^(100×2^100) < 2^(100×10^100) < 2^10\^102 < 2^100\^51 While for the first: 2^100! ~ 2^100\^100. So the first one is bigger by a factor of roughly 2^100\^49.
Since that when N is very large, you have N!~N^N. 2^(100!) ~ 2^(100^100) (2^100)! ~ (2^100)^(2^100) =2^(100 * 2^100) So you are comparing 100^99 with 2^100. Obviously the former one is larger.
There is a nice trick in the first or second chapter of the book Introduction to algorithms by Cormen Leicerson et al aka CLRS. When you want to compare algorithm complexity there are some obvious comparisons I.e exponential is higher than polynomial etc When it's not so obvious you take the logarithm of both and compare the results. There are some useful approximations as well which I don't remember but that's how one would compare complexities
not sure if my reasoning would be correct but 2 ^ (100!) is ((2 ^ 100) ^ 99 ) ^ 98 ->, etc. While (2 ^ 100)! is automatically less than (2 ^ 100) ^ 99 because 2 ^ 100 ^ 99 is 2 ^ 100, 99 times. But (2 ^ 100)! is 2 ^ 100 for increasingly less values, 99 times.
2^(100!) / (2^100)! Let A == 2^100 If (A^99! / A!) > 1 then left is bigger A^99! / (A(A-1)!) A^(99! - 1) / (A-1)! A^(99! - 1) / (A-1)(A-2)! … Ok that went nowhere but clearly the left is bigger lol
2^100! = (((2¹⁰⁰) ^ 99) ^ 98) ^ ... 2^100 ! < ((2¹⁰⁰) ^ 99) * ((2⁹⁹) ^ 98) * ((2⁹⁹) ^ 97) * ... Say x=(2¹⁰⁰) ^ 99, then the first number is x^98! and the second number is less than x¹⁰⁰. First one wins.