Every factorial approximates a power | Hacker News Reader

Every factorial approximates a power

johndcook.com

164 pointswarrenm64 comments

> This is why mathematical libraries will have not only gamma functions but also loggamma functions.

This is super useful for combinatorial problems too, because gamma(N+1) = N!. Some examples where I've used it include:

- Erasure code durability math. The standard approximation has a N!/k! factor (see [1], equation 2.3), which gets out of hand numerically as N gets large. gamma(20) is 1.2e17, while lgamma(20) is only 39.3.

- Hash code collision math. The standard solution (see [2], for example) includes a factor of N!, which is an alarmingly big number when N is 2**128. In these cases, even the lgamma often doesn't fit into a 'double', and you need both logs and arbitrary precision to find exact solutions (better behaved approximations exist).

[1] "Notes on Reliability Models for Non-MDS Erasure Codes" https://dominoweb.draco.res.ibm.com/reports/rj10391.pdf [2] https://en.wikipedia.org/wiki/Birthday_problem

I work on numerical evaluation of special functions. Fyi, typically a better way to evaluate Gamma ratios is to use the Lanczos approximation. See the Boost math documentation [0] for good explanation of the problems with calculating n! / k! as

exp(lgamma(n+1) - lgamma(k+1)).

The form I use for the approximation is:

gamma(x) = factor(x) * lanczos_sum_expg_scaled(x)

where

factor(x) = ((x + lanczos_g - 0.5)/e)*(x - 0.5)

and lanczos_g is a constant.

When dealing with Gamma ratios, you can often cancel the factors nicely, giving a highly accurate approximation which doesn't overflow. It's curious I saw your comment when I did. I was just tinkering with the Lanczos approximation earlier today.

If you use Python, the Lanczos approximation is available in SciPy using

from scipy.special._ufuncs import _lanczos_sum_expg_scaled

and you can use lanczos_g = 6.024680040776729583740234375

[0] https://www.boost.org/doc/libs/1_82_0/libs/math/doc/html/mat...

Replying because I can no longer edit. A * got gobbled. The factor should be

factor(x) = ((x + lanczos_g - 0.5)/e)**(x - 0.5).

I use the Taylor series approximation.

Take your desired probability, say one-in-a-million

   prob = 0.999999

And calculate the bitspace. In this case, 12 base-62 digits

   space = 62 ** 12

Take the natural log of the probability, times -2, times the bitspace. The sqrt of that is approximately the number of items that can be shoved into the bitspace before there is a one-in-a-million chance of collision.

   int(math.sqrt((-2 * math.log(prob)) * space))
    --> 80327683

With 80 million items, the odds of a collision are still 10*6 to 1 against.

A decent approximation to n! is sqrt(2pi n) * (n/e)^n. A worse approximation is that n! is about (n/e)^n.

So, if b(n) is the base in b^n=n!, then b(n) is about (n/e). [I see this as the key observation of the article.]

Keeping in mind that (n/e)^n is a bit smaller than n!, a more accurate value for b(n) is a little higher than n/e.

So it makes sense that 25! ~= 10^25 because 25/e is a bit below 10, and the adjusted value for b(n) ought to be a little higher than 25/e; 10 will do in this case.

(And 270! ~= 100^270, etc.)

Stirling's approximation carried out to more terms gives:

    b = n/e + ln(2πn)/2e + (3(ln(2πn))^2 + 2)/(24en) + o(1/n)

which becomes a good approximation for large n: https://colab.research.google.com/drive/17cC8YUqKjEBLsNJkJ4I...

Yes! I'm surprised he didn't mention that the factor is e.

You can also use Bertrand's postulate to show that no non-trivial factorial equals a perfect integer power greater than 1.

An interesting question is whether you can show this without resorting to Bertrand's postulate.

Because {2..n} contains some prime p, in the range n/2 < p < n, which appears exactly once in the factorization of n!. (Is that the argument?)

Correct.

You're going to need some kind of result on the occurence of primes at least, because if you remove all factors greater than some prime you trivially get perfect powers (e.g. 6! ≈ 12² if you ignore the factor 5).

(After thinking about it some more, perhaps not trivially.)

Can somebody explain to me why 24! ≈ 10^24 and 25! ≈ 10^25 makes sense?

25! is 25 times bigger than 24! while 10^25 is 10 times bigger than 10^24?

Those are very rough approximations: 24! is about 60% of 10^24 and 25! is about 155% of 10^25.

It's simpler to remember that 24.5! ≈ 10^24.5 (accurate to within +/- 3%; see https://www.wolframalpha.com/input?i=solve+x%21+%3D+10%5Ex)

The old saying:

    2 + 2 = 5 for large values of "2"

It's an approximation. The sentence is perhaps confusing since it might imply that n! ≈ 10^n but that's not the case, the article uses 24 and 25 as the cut point where the approximation is true.

The linked post is more informative: https://www.johndcook.com/blog/2023/06/22/mentally-approxima...

A simpler way to think of the approximation is that 24! multiples together all fifteen numbers from 10 to 24, all of which add at least another power of 10, and you get approximately another nine powers of ten from multiplying in 1 through 9. You end up around 6.2e23 which rounds up to the approximation.

Going up to the next factorial bumps it up (approximately) another power of ten since you are multiplying by 2.5 and 10. In reality it’s around 1.5e25 which is also a reasonable approximation.

Over simplification: a number times 25 is closer to the number times 10 than it is to the number times 100.

Because 25! = 25*(24!), and 25 itself is 100/4. So 25! = 10*(10/4)*24! Now since we are given 24! ~10^24, it follows that 25! ~ (10/4)*10^25. But 10/4 is just a bit over 2, not a strong enough multiplicative factor to break the "approximately equals relationship". Therefore 25! ~ 10^25. QED

Took me a while to get it. The point is more that if you want x! ≈ 10^x then these are as good as you'll get. The ≈ is very very approximate though!

They are not equal, nor approximate either. In this text they kinda use the approximation sign (≈) more like "same order of magnitude". Because if you do a comparison you find out that it's a 60% error between those numbers.

If you’re into that kind of thing, here is an article about the historical development of the gamma function: http://sgpwe.izt.uam.mx/files/users/uami/jdf/proyectos/Euler...

I've no idea how this could be so relevant to people but I'm enjoying how excited some are in this comments section.

The basic approximation I use is n! ~ (n/e)^n so ln(n!) ~ n(ln(n)-1). The basic inequality is (n/e)^n < n! < (n/e)^{n+1}. When considering convergence of series using the n-th root test, (n!)^{1/n} ~ n/e so ((an)!)^{1/n} = (((an)!)^{1/(an)})^a ~(an/e)^a = a^an^a/e^a.

(x!)^(1/x) ~ x/e

better: (x!)^(1/x) ~ x/e - 1.8 * ln(ln(x))

https://www.wolframalpha.com/input?i=+%28x%21%29%5E%281%2Fx%...

For people wondering why this isn’t obvious:

> What’s interesting is that b is very nearly a linear function of n.

What makes it so close to linear but not perfectly?

Saying (2n)! ≈ 2^(2n)*(n!)^2 means he's approximating the central binomial coefficient (2n choose n) as 2^(2n). In reality, 2^(2n) is really the sum of all binomial coefficients (2n choose k) for k=0..2n. So clearly this is going to be an underestimate, as we're approximating the sum of 2n terms by only one of them.

However, since the biggest term in the sum of 2n positive numbers is clearly within a factor 2n of the entire sum, the ratio of the logarithms is at least log(2^(2n) / 2n) / log(2^(2n)) = 1-log(2n)/(2n) which converges to one pretty quickly.

And, in fact, a tighter analysis would show that the error decreases faster than what I outlined.

(sorry, that's the sum of 2n+1 terms, but the analysis doesn't appreciably change)

The fact that Sterling’s approximation is only an approximation

If you are allowed to use R for base and exponent then this is tautological because Z is a tiny subset of R. And factorials are by definition in Z, which is closed under multiplication. If the linear relationship is the interesting part then lead with that.

$exp(log n! / n)$

is the same as

   $(n!)^(1/n)$

which is obviously what the article is about.

Why write it the complicated way? Are `exp` and `log` more usable than $^n$ in some context?

> For every n, there is some base b such that n! = b^n. For example, 30! ≈ 1230.

False. Probably the author meant to use "≈" twice.

I was confused by that.

And I'm still confused. What does "≈" mean, exactly? Is 2+2≈3^^3?

>For every n, there is some base b such that n! = b^n. For example, 30! ≈ 12^30

I think missing here is that "=" should be a "≈", and that "b" should be an integer. Otherwise this is trivially false (consider 2!=b^2 if b must be integer) or true (if b need not be integer).

It is the trivial case, b = exp(log(n!)/n)

  30! = 12.04449703813164.... ** 30

It's leading on to the next part: "What’s interesting is that b is very nearly a linear function of n. In hindsight it’s clear that this should be the case—it follows easily from Stirling’s approximation—but I didn’t anticipate this before I plotted it."

Am I misreading the article, or is it actually saying that every factorial is approximately a power? The title makes it sound like it's exactly a power.

Every number is a power if you allow non-integers. But it seems indeed like it means _near_ an integer power in this case. The factorial of 3 is 6 but 6 is not a non-trivial integer power of anything. I don't like the title either.

The article also says, you can find a base b such that n! = b^n for any factorial. Guess what, you can do this for any number x and any n to find b such that x = b^n, whether x is a factorial or not: b is x ^ (1/n). Not sure what Stirling's approximation should have to do with this, and why = and ≈ are being used inconsistently in this post.

Ignoring my complaints of this particular post, this is a pretty great blog though, and I remember being helped by the linked older blog post article about log1p and expm1 before!

The Stirling's approximation part of it is about why exp(log(n!)/n) is nearly linear. I think what he's saying is basically: if you take the log version of Stirling's approximation, ln(n!) = n*ln(n) - n + O(ln(n)), ignore the big O term, then divide both sides by n and take e to the power of each side, you get the formula for the `b` from the article on the left, and n/e on the right, which is linear.

I've never actually worked with Stirling's approximation, but I guess if you have a certain set of context, this fact would be obvious?

The Stirling's approximation is a good way to implement an accurate gamma function approximation on PC/calculators/..., but it's just a formula to implement, it doesn't necessarily mean you think about fun facts like this while implementing it...

Rational numbers yes.

Irrational Number: I'm a non-integer, Greg. Can you square root me?

well it got your attention enough that you appeared to have read at least some of the article so i guess that's a win. everyone got to hustle.

> everyone got to hustle.

Why?

Scroll down below the article:

> My colleagues and I have decades of consulting experience helping companies solve complex problems involving data privacy, math, statistics, and computing.

> Let’s talk. We look forward to exploring the opportunity to help your company too.

Getting more attention then clarifying the intent in the body is sometimes mischievous (read: every tabloid newspaper), but it nonetheless brings more good attention that it would have without the click bait. If that leads to more consulting work for the author, good for him.

(it kind of feels weird calling a high-number approximation “clickbait” but, in some circles…)

"Did you like my article wherein I misunderstand a mathematical concept? Hire me to do math for you!" doesn't seem to be a strong pitch...

I think it’s clear to the author and every reader that it wasn’t a misunderstanding.

I think it really is exactly a power, as long as `b` is allowed to be any real number.

Every positive number is exactly a power if you allow that.

Yup. I got hung up on that too. I think the article could have better stated it as:

  For every natural n, there exists a natural b, such that: n! ≈ b^n

I don't quite know the precise criteria for "≈" here, that's a bit beyond my understanding of the article...

≈ is a loose approximation.

The fact is that `e * (n!)^(1/n)` is quite close to `n`.

But John didn't factor out the `e`, causing the confusion in this HN post's threads.

He also mis-typesets it as = on the same line! Very confusing.

Every positive number is in fact (uncountably) infinitely many powers in this case.

so you're saying the title is accurate

It's either inaccurate or trivial depending on how you interpret it:

- If you only allow the base to be an integer, then it's inaccurate.

- If you allow the base to be a real number, then you're really just saying "every factorial is a positive number", which is a trivial fact if you know what a factorial is.

Either way it's a bad title IMO.

yes it's clickbait, which is sad because that blogger is an OG computational science popularizer

EDIT: whoever is downvoting me, the article title is objectively clickbait

I spent approximately as much time trying to understand this aspect as I did what the author was actually saying.

The language is annoyingly misleading, and the seemingly random use of = and ≈ is frustrating.

Either my math or my english is failing me.

The integer examples really threw me off too.

6.20 ≈ 10.00; 1.55 ≈ 1.00; 2.37 ≈ 2.65

> 6.20 ≈ 10.00

That's like when my friend tortured her kid (and me) by asking how old I was, which was answered with "75". That is a very wide margin of error there.

Well, worst case they are exactly something power to 1

It’s just a power of a non integer base, which he gives a formula for

This is either incorrect or it does not really mean anything, depending on how you look at it.

It’s Stirling’s approximation, as the article mentions. The formula uses the ≈ character. The Wikipedia article gives bounds on the error—

https://en.wikipedia.org/wiki/Stirling's_approximation

but then isn't every integer a power of a (non integer) base? In this interpretation the statement is pretty useless.

And he really doesn't give a very nice formula for it.

Numerically, the point of the article is the fact that

n! \approx (0.826523 + n*0.373522)^n

For n in the range from 10 to 50, this is within 5% of the right answer.

But I really don't see that this is all that much simpler than Stirling's approximation and it is considerably less accurate and not asymptotically very good. Stirling's formula is within about 1% for all n>10 and within 0.1% for n>90.

Actually computing gamma(n) or lgamma(n) to high precision requires a bit more effort than this, but as an approximation, Stirling's formula is really pretty good.

Yeah, you are correct.

Ok we've made the title approximate now.

Reply on news.ycombinator.com