[HN Gopher] Every factorial approximates a power
___________________________________________________________________
Every factorial approximates a power
Author : warrenm
Score : 132 points
Date : 2023-06-26 13:24 UTC (9 hours ago)
(HTM) web link (www.johndcook.com)
(TXT) w3m dump (www.johndcook.com)
| ykonstant wrote:
| 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 wrote:
| 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 wrote:
| Correct.
| contravariant wrote:
| 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! [?] 122 if
| you ignore the factor 5).
|
| (After thinking about it some more, perhaps not trivially.)
| zmgsabst wrote:
| For people wondering why this isn't obvious:
|
| > What's interesting is that b is very nearly a linear function
| of n.
| hammock wrote:
| What makes it so close to linear but not perfectly?
| [deleted]
| CaptainNegative wrote:
| 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 wrote:
| (sorry, that's the sum of 2n+1 terms, but the analysis
| doesn't appreciably change)
| qbit42 wrote:
| The fact that Sterling's approximation is only an
| approximation
| FartyMcFarter wrote:
| 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.
| bannedbybros wrote:
| [dead]
| gcanyon wrote:
| 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.
| dang wrote:
| Ok we've made the title approximate now.
| shultays wrote:
| Well, worst case they are exactly something power to 1
| gautamcgoel wrote:
| Yeah, you are correct.
| ftxbro wrote:
| 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.
| glitchc wrote:
| > everyone got to hustle.
|
| Why?
| whyhustle wrote:
| [flagged]
| i-use-nixos-btw wrote:
| 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...)
| gowld wrote:
| "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...
| qbit42 wrote:
| It's just a power of a non integer base, which he gives a
| formula for
| dietrichepp wrote:
| 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
| mqus wrote:
| but then isn't every integer a power of a (non integer) base?
| In this interpretation the statement is pretty useless.
| ted_dunning wrote:
| 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.
| aimor wrote:
| The integer examples really threw me off too.
|
| 6.20 [?] 10.00; 1.55 [?] 1.00; 2.37 [?] 2.65
| hinkley wrote:
| > 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.
| sapiogram wrote:
| I think it really is exactly a power, as long as `b` is allowed
| to be any real number.
| FartyMcFarter wrote:
| Every positive number is exactly a power if you allow that.
| ftxbro wrote:
| so you're saying the title is accurate
| FartyMcFarter wrote:
| 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.
| ftxbro wrote:
| 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
| c7b wrote:
| Every positive number is in fact (uncountably) infinitely
| many powers in this case.
| kdmccormick wrote:
| 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...
| throwawaymaths wrote:
| He also mis-typesets it as = on the same line! Very
| confusing.
| gowld wrote:
| [?] 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.
| Aardwolf wrote:
| 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!
| mistercow wrote:
| 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?
| Aardwolf wrote:
| 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...
| hinkley wrote:
| Rational numbers yes.
|
| Irrational Number: I'm a non-integer, Greg. Can you square
| root me?
| slavapestov wrote:
| 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...
| lifeinthevoid wrote:
| 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 wrote:
| 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.
| hinkley wrote:
| The old saying: 2 + 2 = 5 for large values of
| "2"
| kevmo314 wrote:
| 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...
| quickthrower2 wrote:
| 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 wrote:
| 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
| mathgeek wrote:
| 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.
| warrenm wrote:
| >For every n, there is some base b such that n! = b^n. For
| example, 30! [?] 12^30
| colanderman wrote:
| 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 wrote:
| 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."
| gowld wrote:
| $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?
| mjb wrote:
| > 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
| steppi wrote:
| 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...
| steppi wrote:
| 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).
| aristus wrote:
| 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.
| gowld wrote:
| (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%...
| psychphysic wrote:
| I've no idea how this could be so relevant to people but I'm
| enjoying how excited some are in this comments section.
| mjcohen wrote:
| 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.
| tylerneylon wrote:
| 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 wrote:
| Yes! I'm surprised he didn't mention that the factor is e.
| garbagecoder wrote:
| 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.
| MathMonkeyMan wrote:
| > 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 wrote:
| I was confused by that.
|
| And I'm still confused. What does "[?]" mean, exactly? Is
| 2+2[?]3^^3?
___________________________________________________________________
(page generated 2023-06-26 23:01 UTC)