6 ms·

Every factorial approximates a power

164 points by warrenm 3y ago

warrenm 3y ago
>For every n, there is some base b such that n! = b^n. For example, 30! ≈ 12^30
- colanderman 3y ago
  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).
  - eesmith 3y ago
    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."
zmgsabst 3y ago
For people wondering why this isn’t obvious: > What’s interesting is that b is very nearly a linear function of n.
- hammock 3y ago
  What makes it so close to linear but not perfectly?
  - qbit42 3y ago
    The fact that Sterling’s approximation is only an approximation
  - deleted 3y ago
    [deleted]
  - CaptainNegative 3y ago
    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.
    - CaptainNegative 3y ago
      (sorry, that's the sum of 2n+1 terms, but the analysis doesn't appreciably change)
FartyMcFarter 3y ago
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.
- gautamcgoel 3y ago
  Yeah, you are correct.
- qbit42 3y ago
  It’s just a power of a non integer base, which he gives a formula for
  - dietrichepp 3y ago
    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 https://en.wikipedia.org/wiki/Stirling's_approximation
  - mqus 3y ago
    but then isn't every integer a power of a (non integer) base? In this interpretation the statement is pretty useless.
  - ted_dunning 3y ago
    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.
- sapiogram 3y ago
mjb 3y ago
> 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 https://dominoweb.draco.res.ibm.com/reports/rj10391.pdf [2] https://en.wikipedia.org/wiki/Birthday_problem https://en.wikipedia.org/wiki/Birthday_problem
- aristus 3y ago
  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.
- steppi 3y ago
  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/math_toolkit/lanczos.html https://www.boost.org/doc/libs/1_82_0/libs/math/doc/html/mat...
ykonstant 3y ago
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.
- perihelions 3y ago
  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?)
  - ykonstant 3y ago
    Correct.
- contravariant 3y ago
  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.)
slavapestov 3y ago
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_integral.pdf http://sgpwe.izt.uam.mx/files/users/uami/jdf/proyectos/Euler...
lifeinthevoid 3y ago
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?
- unnouinceput 3y ago
  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.
- kevmo314 3y ago
  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-approximating-factorials/ https://www.johndcook.com/blog/2023/06/22/mentally-approxima...
- mathgeek 3y ago
  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.
- quickthrower2 3y ago
  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!
- IIAOPSW 3y ago
  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
psychphysic 3y ago
I've no idea how this could be so relevant to people but I'm enjoying how excited some are in this comments section.
tylerneylon 3y ago
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.)
- bo1024 3y ago
  Yes! I'm surprised he didn't mention that the factor is e.
- svat 3y ago
  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/17cC8YUqKjEBLsNJkJ4IxA_LKDdg9Hflv https://colab.research.google.com/drive/17cC8YUqKjEBLsNJkJ4I...
MathMonkeyMan 3y ago
> 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.
- jfengel 3y ago
  I was confused by that. And I'm still confused. What does "≈" mean, exactly? Is 2+2≈3^^3?
gowld 3y ago
$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?
mjcohen 3y ago
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.
gowld 3y ago
(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%29+-%28x%2Fe+%2B+1.8+*+ln%28ln%28x%29%29%29%2C+x+from+0+to+1e14 https://www.wolframalpha.com/input?i=+%28x%21%29%5E%281%2Fx%...
garbagecoder 3y ago
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.

164 points by warrenm 3y ago

warrenm 3y ago

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

colanderman 3y ago
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).
- eesmith 3y ago
  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."

zmgsabst 3y ago

For people wondering why this isn’t obvious: > What’s interesting is that b is very nearly a linear function of n.

hammock 3y ago
What makes it so close to linear but not perfectly?
- qbit42 3y ago
  The fact that Sterling’s approximation is only an approximation
- deleted 3y ago
  [deleted]
- CaptainNegative 3y ago
  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.
  - CaptainNegative 3y ago
    (sorry, that's the sum of 2n+1 terms, but the analysis doesn't appreciably change)

FartyMcFarter 3y ago

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.

gautamcgoel 3y ago
Yeah, you are correct.
qbit42 3y ago
It’s just a power of a non integer base, which he gives a formula for
- dietrichepp 3y ago
  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 https://en.wikipedia.org/wiki/Stirling's_approximation
- mqus 3y ago
  but then isn't every integer a power of a (non integer) base? In this interpretation the statement is pretty useless.
- ted_dunning 3y ago
  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.
sapiogram 3y ago

mjb 3y ago

> 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 https://dominoweb.draco.res.ibm.com/reports/rj10391.pdf [2] https://en.wikipedia.org/wiki/Birthday_problem https://en.wikipedia.org/wiki/Birthday_problem

aristus 3y ago
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.
steppi 3y ago
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/math_toolkit/lanczos.html https://www.boost.org/doc/libs/1_82_0/libs/math/doc/html/mat...

ykonstant 3y ago

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.

perihelions 3y ago
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?)
- ykonstant 3y ago
  Correct.
contravariant 3y ago
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.)

slavapestov 3y ago

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_integral.pdf http://sgpwe.izt.uam.mx/files/users/uami/jdf/proyectos/Euler...

lifeinthevoid 3y ago

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?

unnouinceput 3y ago
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.
kevmo314 3y ago
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-approximating-factorials/ https://www.johndcook.com/blog/2023/06/22/mentally-approxima...
mathgeek 3y ago
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.
quickthrower2 3y ago
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!
IIAOPSW 3y ago
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

psychphysic 3y ago

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

tylerneylon 3y ago

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

bo1024 3y ago
Yes! I'm surprised he didn't mention that the factor is e.
svat 3y ago
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/17cC8YUqKjEBLsNJkJ4IxA_LKDdg9Hflv https://colab.research.google.com/drive/17cC8YUqKjEBLsNJkJ4I...

MathMonkeyMan 3y ago

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

jfengel 3y ago
I was confused by that. And I'm still confused. What does "≈" mean, exactly? Is 2+2≈3^^3?

gowld 3y ago

$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?

mjcohen 3y ago

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.

gowld 3y ago

(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%29+-%28x%2Fe+%2B+1.8+*+ln%28ln%28x%29%29%29%2C+x+from+0+to+1e14 https://www.wolframalpha.com/input?i=+%28x%21%29%5E%281%2Fx%...

garbagecoder 3y ago

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.