hackernews client

How big are factorials?

97 pointsposted 5 days ago

(eli.thegreenplace.net)

45 Comments

svobodamartin

4 days ago

My favorite one is with the 52! seconds:

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.

https://sites.imsa.edu/hadron/2025/02/26/how-big-is-52/

avmich

a day ago

I think you might enjoy these stories - https://www.mrob.com/pub/math/largenum.html

svobodamartin

8 hours ago

That's solid large number's bible, thanks!

ikesau

4 days ago

Holy hell, this is great.

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.

hermitcrab

4 days ago

I tried something along the same lines, but not just for size:

http://howmanyelephants.co.uk/

davidnc

4 days ago

For another perspective, 52! is roughly the number of atoms in a galaxy. Galaxies are really quite large!

theturtletalks

4 days ago

There are more way to rearrange a deck of cards than there are stars in the universe

ninju

4 days ago

The author's casual mention of 52! at the opening of the article triggered an OLD webpage that I saw many years ago

https://czep.net/weblog/52cards.html

Anyone know how to determine the age of this page (it's got be at least 20yrs old)

stronglikedan

4 days ago

52 cards is the first thing I think of when I think factorials. It's such a great and relatable way to convey the subject to people, plus it usually ends up blowing their minds like it did mine when I first learned of it. Not from this page, but from a YT vid many moons ago.

TheRealPomax

4 days ago

The main.css file it imports dates itself to March 9 of 2005, and is housed in an "ancient history" section of the website that covers everything before October 26, 2010, so: "sometime between those two years" =P

DavidSJ

4 days ago

Its first appearance on the WayBack Machine is October 13, 2009, which narrows the range somewhat.

Dwedit

4 days ago

It was made during the brief XHTML craze. (And it's also invalid XHTML)

rileymat2

4 days ago

I still kind of have a soft spot for XHTML, semantic web and progressive enhancement.

benatkin

4 days ago

To me it feels like a smuggled exponentation. If I take half of 52 and raise it to itself and add a base unit to it like grams or meters, that's an incomprehensibly large amount.

andrewla

4 days ago

This brings to mind the analysis in Bender & Orszag; they approach this through difference equations (a bit of a lost art in formal mathematics; very 19th-century feel) rather than integration.

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.

movpasd

4 days ago

Stirling's approximation is also used a lot in statistical mechanics, because you often have to calculate logs of state space sizes, which means lots of combinatorics and thus lots of factorials. Plus it's continuous so you can do calculus.

Sharlin

4 days ago

A quick and dirty approximation of the number of digits in n! is n lg n, which approximates n! from above, via the inequality

  1 * 2 * … * n ≤ n * … * n.

(This approximation should be familiar to many from an algorithmics class.)

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).

qsort

4 days ago

> (This approximation should be familiar to many from an algorithmics class.)

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.

Sharlin

4 days ago

Sure, I could've said "upper bound" :P

abetusk

4 days ago

lg(n!) grows roughly as (n lg n). Constants matter, of course, but to that's the rough estimate.

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.

thechao

4 days ago

My kids love taking about big numbers. TREE(3) is a family favorite. So, I was going over sequences with them, and I decided to go slow instead. My sequence was: 1 1 1 1 ... 1 ...

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!)

astrojams

4 days ago

I've struggled to understand how TREE(3) works and why it grows so big. I once posted to Math.Stackexchange many years ago and got a professor to help explain it to me: https://math.stackexchange.com/questions/313134/why-is-tree3...

I also loved David Metzler's series on ridiculously big numbers: https://www.youtube.com/playlist?list=PL3A50BB9C34AB36B3

user

4 days ago

[deleted]

mohamedmohey

3 days ago

This reminded me of tetration and Knuth's up-arrow notation. It's basically repeated exponentiation.

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.

cwmoore

3 days ago

I came across an interesting feature of factorials while making the puzzle books at https://www.kakurokokoro.com

The widest two rows are nine digits across, but while the first can be any of arrangements of the digits 1-9, the second cannot repeat any digits in the same columns, and so it limits allowable permutations to the number of derangements — which is close to 9!/e (where e is Euler’s Constant 2.718…)

No idea what this has to do with the relationship of i and pi.

pagade

4 days ago

Reminds me of: Professor asked us to find the biggest factorial using C programming language. And then using LISP. You can imagine our surprise.

pkaye

4 days ago

There is a algorithm call Prime Swing Factorial that can compute large factorials exactly in arbitrary precision math using prime factorization. Like 10000000! in under second depending of how optimized the math library it. Probably like 100x faster than the normal method.

anthk

4 days ago

With Lisp you can use iterative algos and get that under a second too. SBCL can be ridiculously fast; and if you optimize the compilation for integers... the speed gets really close to your solution.

flcikfinder

4 days ago

Worth noting for anyone reaching for this in practice rather than out of curiosity: several standard library implementations (Python's math.factorial is one) already use a divide-and-conquer multiplication scheme instead of naive sequential multiplication for exactly this reason, so you often get most of that speedup for free without implementing prime swing yourself.

smcin

4 days ago

(I just undead'ed this comment; can't see why it was downvoted.)

smcin

4 days ago

I think you mean "using base C without any arbitrary-precision library (e.g. GMP)" . All that illustrates is that Lisp has built-in support for arbitrary-precision arithmetic, whereas C doesn't. Otherwise, how is this surprising, and what is the reason for the performance difference?

hermitcrab

4 days ago

60! is more than the number of atoms in the observable universe. This is why wedding seating plans are hard. ;0)

brudgers

5 days ago

Factorial (n) for n > 24 is greater than 10^n.

saalweachter

4 days ago

24! is approximately Avogadro's number (about a 3% difference).

smcin

4 days ago

inverse Gamma function of Avogadro's number (6.02 × 10²³) is ~ 24.99056

saalweachter

4 days ago

Sure, but "23.99067408! is Avogadro's number" is both harder to remember and less cool than "24! is almost Avogadro's number".

smcin

4 days ago

Sure. I wasn't disagreeing with you; just curious how close the coincidence was.

emil-lp

4 days ago

What's surprising (to many) is that

n! < exp(n log n)

Someone

4 days ago

> What's surprising (to many) is that

> 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

and it’s not surprising that

    1 × 2 × 3 × 4 × … × n
  < n × n × n × n × … × n

for n > 1

emil-lp

4 days ago

I don't know why that is surprising, but I'm teaching computer science at a university, and students seem surprised every time it comes up.

user

4 days ago

[deleted]

anthk

4 days ago

I did factorials even under KLISP 23 with cons cells as fake integers:

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).