Preloader

How big are factorials?

Technology
by admin -
0

The other day, I found myself wondering how big 52! (52 factorial) is,
and that led me to ponder how these could be estimated without a
calculator or a computer.

It turns out there’s some fairly interesting math behind being able to
estimate the size (number of digits) of a factorial reasonably
accurately. This post will start by stating how to do the estimate, and
if you’re curious you can read on for the math background.

Without further ado, the approximation is:

[text{number of digits in n!}approx nlog_{10}left(frac{n}{e}right)+2]

As an example, let’s use my original question, by estimating this for
52!

Well, 52 divided by e is… 20-ish? And log_{10}(20) is
about 1.3 [1]; therefore our estimate comes out to:

[text{number of digits in 52!}approx 52cdot 1.3 +2 approx69]

The real answer is 68, so this is very close! In estimates like this –
when you’re dealing with enormous numbers – being off by a couple of
digits usually isn’t a big deal.

The Gamma function

The Gamma function for real n>0 is defined [2] as:

[Gamma(n)=int_{0}^{infty}x^{n-1}e^{-x}dx]

This integral does not have an analytic expression in the general case,
but it does have a very useful property that we can take advantage of.
Let’s see what Gamma(n+1) is:

[Gamma(n+1)=int_{0}^{infty}x^{n}e^{-x}dx]

And now use integration by parts with:

[u=x^nqquad v=-e^{-x}]

Then:

[du=nx^{n-1} dxqquad dv=e^{-x}dx]

So:

[begin{aligned}
Gamma(n+1)&=int_{0}^{infty}x^{n}e^{-x}dx\
&=left. -x^n e^{-x}right|_{0}^{infty}-int_{0}^{infty}-e^{-x}n x^{n-1}dx\
&=nint_{0}^{infty}x^{n-1}e^{-x}dx
end{aligned}]

But notice that the last integral is just Gamma(n); therefore,
we’ve shown that:

[Gamma(n+1)=nGamma(n)]

Let’s also calculate Gamma(1) – it’s a special case that has an
analytical solution:

[Gamma(1)=int_{0}^{infty}e^{-x}dx=left. -e^{-x}right|_{0}^{infty}=1]

This helps establish an induction argument:

[begin{aligned}
Gamma(2)=1cdotGamma(1)&=1!\
Gamma(3)=2cdotGamma(2)&=2!\
Gamma(4)=3cdotGamma(3)&=3!\
dots\
Gamma(n+1)=ncdotGamma(n)&=n!
end{aligned}]

In other words – the Gamma function is an interpolation of the factorial
over all positive reals. Here’s a plot of the Gamma function over a
small range; note that the y axis is log-scale because of the function’s
fast growth:

Gamma function plot

Stirling’s approximation

You may have encountered Stirling’s approximation before:

[n!approxsqrt{2pi n}cdotleft(frac{n}{e} right)^n]

It’s a great approximation that works reasonably well even for small
n. This section is a brief overview of how Stirling’s formula is
derived from the Gamma function.

Taking:

[n!=Gamma(n+1)=int_{0}^{infty}x^n e^{-x}dx]

We’ll start by massaging the integrand a bit:

[n!=int_{0}^{infty}x^n e^{-x}dx=int_{0}^{infty}e^{n ln x} e^{-x}dx]

And making a change of variables x=ny, which means that
dx=ndy:

[begin{aligned}
n!&=int_{0}^{infty}ne^{nln(ny) – ny}dy=nint_{0}^{infty}e^{n(ln n+ln y-y)}dy\
&=ne^{nln n}int_{0}^{infty}e^{n(ln y-y)}dy
end{aligned}]

These steps make the integral amenable to applying Laplace’s
method, which allows
us to approximate definite integrals of the form:

[int_{a}^{b}e^{nf(x)}dx]

Where f(x) is a twice-differentiable function and n some
large number. By Laplace’s method, such integrals can be approximated
by:

[int_{a}^{b}e^{nf(x)}dxapproxsqrt{frac{2pi}{n|f”(x_0)|}}e^{n f(x_0)}]

Where x_0 is the global maximum of f(x).

Let’s see how to apply this method [3] to the latest equation we have
for n! (renaming the dummy integration variable back to
x):

[n!=ne^{nln n}int_{0}^{infty}e^{n(ln x-x)}dx]

In our case, f(x)=ln x – x. It’s easy to show that this
function is twice differentiable and has a global maximum at
x_0=1. Moreover:

[begin{aligned}
f(x_0)&=-1\
f”(x_0)&=-1\
end{aligned}]

Substituting these into the proper places in Laplace’s approximation, we
get:

[begin{aligned}
n! &approx ne^{nln n}sqrt{frac{2pi}{n}}e^{-n}\
&approx sqrt{2pi n}cdot e^{n(ln n – 1)}\
&approx sqrt{2pi n}cdot left(frac{n}{e}right)^nquadblacksquare
end{aligned}]

Number of digits from Stirling’s approximation

We can calculate the number of digits in n! by taking the
base-10 logarithm of Stirling’s formula:

[begin{aligned}
text{number of digits in n!}&approx log_{10} left(sqrt{2pi n}cdot
left(frac{n}{e}right)^nright)\
&approx log_{10}left(sqrt{2pi n}right)+ log_{10}left(frac{n}{e}right)^n\
&approx log_{10}left(sqrt{2pi n}right)+ ncdot log_{10}left(frac{n}{e}right)
end{aligned}]

Note that the first term is not multiplied by n itself;
therefore, as n grows, it will become less and less noticeable.
That said, it still adds a couple of digits – so you should take it into
account if you want a more accurate approximation [4]

[1] Mental tricks for calculating log_{10} is a different topic,
but it really helps to remember that log_{10}2=0.3,
log_{10}3=0.5, and from here using the various logarithm
laws to estimate multiples.
[2] As a matter of fact, the Gamma function is defined for complex
numbers, but for our purpose talking about the reals is sufficient.
[3] As much as I’d like to dive into why this approximation works, the
rabbit hole in this post is already deep enough!
[4] It adds up to 2 extra digits as long as n is less than 1600
or so, and may add more than 2 after that, though no more than 3
until n is 160000. It’s not clear why anyone would like to estimate
the number of digits of 1600! (about 4450, in case you were
wondering), let alone 160000!

For comments, please send me
an email.

Source: Hacker News

Choose your Reaction!
Leave a Comment
Related Articles
News Technology
South Korea says AI agents appear to have been used to hack the country's banks

South Korean authorities announced that a series of recent cyber intrusions into the nation’s banking sector were carried out with the help of advanced artificial‑intelligence agents. The attacks, which began in early March, targeted three major banks, compromising customer accounts and siphoning small amounts of funds before the breaches were detected. Investigators say the AI systems were used to automate the reconnaissance phase, identify vulnerable points in the banks’ networks, and deploy malware that could adapt to defensive measures in real time.nnThe technical analysis revealed that the attackers employed machine‑learning algorithms to generate highly realistic phishing emails, increasing the success rate of credential theft. Once inside, the AI‑driven malware scanned for transaction authorization codes and exploited zero‑day vulnerabilities in the banks’ core banking software. The rapid, self‑learning nature of the attacks allowed the perpetrators to evade traditional security tools and reduce the window of exposure to just a few hours.nnIn response, the Korean Financial Services Commission has launched a joint investigation with the National Police Agency and the Cyber Security Center. The agencies are reviewing the banks’ incident‑response protocols, strengthening multi‑

by admin -
16
0