https://czep.net/weblog/52cards.html
Anyone know how to determine the age of this page (it's got be at least 20yrs old)
1 * 2 * … * n ≤ n * … * n.
For a tighter bound, use n lg n - n/2, or a better approximation of ln 10 in place of 1/2 if you wish. This comes from Stirling's approximation which notes that
ln n! = n ln n - n + O(ln n).You need both sides though :)
What makes it interesting for estimating algorithmic complexity is that \log{n!} \in \Theta(n \log n). One side is obvious as you note, the other less so, but there's a famous trick to do both at once:
\log{n!} = \log{\prod_{h=0}^{n} h} = \sum_{h=0}^{n} \log{h}
Therefore,
\int_0^n \log{x} dx \le \log{n!} \le \int_0^n \log{x+1} dx
with both integrals trivial by parts.
As an aside, if you take numbers from 0 to (n-1) in an array, there are n! configurations, so representing each configuration or differentiating each configuration take n lg n bits. So, in some sense, taking a mapping that's able to differentiate the input state to map to the ordered state takes at least O(n lg n) time, the standard runtime of a basic sorting algorithm.
Any additional assumptions (n larger than maximum element, distribution of elements) helps reduce this.
They accused me of using just "all 1s" (which is, naturally, cheating). Ai contraire!
The count of the number of digits in the decimal representation of the number of unique primes in the prime factorization of the natural numbers.
The best part is that even pretty young kids can compute this sequence; by the first "2" is at 2*3*5*7*11*13*17*19*23*29!
(Hopefully I got that right; the phone doesn't make it easy to type!)
I also loved David Metzler's series on ridiculously big numbers: https://www.youtube.com/playlist?list=PL3A50BB9C34AB36B3
https://t3x.org/klisp/22/index.html
Dog slow but the old n270 netbook (32 bit) handles big factorials >20 fine, and OFC it's instant under Common Lisp (SBCL) and Scheme (both S9 and Chicken).
Instead of introducing the gamma function, they instead start from the observation that log(F_n) - log(F_n-1) = log(n), so treating this difference as analogous to integration, it says that F_n ~= nlogn + n as the leading asymptotic behavior. This is clear just by substitution and algebra; no calculus necessary (though it helps to "know the answer beforehand").
From there you can treat the error term in this as F_n = n^n * e^n * E_n and plug that into the same relationship (F_n = n * F_n-1) to derive what that error term looks like asymptotically, and end up in the same place that the integration on the OP leads to.
n! < exp(n log n)
> n! < exp(n log n)
Why would that be surprising? I can see that many wouldn’t know whether it’s true, but
exp(n × log n) =
exp(log(n) × n) =
exp(log(n))^n =
n^n
1 × 2 × 3 × 4 × … × n
< n × n × n × n × … × n
Start a timer that will count down the number of seconds from 52! to 0. Then walk around the Earth’s equator with one step every billion years. Then, after you make your way around the earth equator (by taking 1 step every billion of years), you take one drop of water out of the Pacific Ocean. Then, you repeat the process of walking around the equator, and everytime you walk around, you keep draining one singular drop of water. After the ocean is fully drained, you refill the ocean and put a piece of paper underneath you. Now, you once again repeat this process of walking, draining, and placing papers. After your stack of papers has reached the Sun, you repeat another 1000 times.
After all this, you have completed just about a third of the timer.
I once made a little tool for getting more intuitive spatial scales for things in the universe at https://observablehq.com/@ikesau/scale-to-the-universe
I feel like you could do something similar for these sorts of "fathom this large number" recipes.
Searching now, I just learned of tetrofactorial, which is a factorial using tetration operations. There's also pentation which is repeated tetration.
And there's a whole wiki for it here: googology.fandom.com
It's fun because the numbers are so big it's basically infinity but any of those numbers is still nothing compared to infinity.