Factorial equations

Dec 2015
1,082
169
Earth
How to solve without inspection , for \(\displaystyle n \) -natural
1) \(\displaystyle n!=1\)
2) \(\displaystyle n!=2\)
3) \(\displaystyle n!=6\)
 
May 2016
1,310
551
USA
I have no idea what this question even means. Are you asking whether there is a mystical process whereby you can evaluate 23! without computation?

One way to define the factorial operation on non-negative integers is

$n \in \mathbb Z_{\ge 0} \implies$

$n! = 1 \text { if } n = 0 \text { and }$

$n! = n * (n - 1)! \text { if } n > 0.$

But to determine what number is equal to 23!, what kind of process are you looking for that does not involve any arithmetic?
 

SDK

Sep 2016
801
543
USA
How to solve without inspection , for \(\displaystyle n \) -natural
1) \(\displaystyle n!=1\)
2) \(\displaystyle n!=2\)
3) \(\displaystyle n!=6\)
What does "without inspection" mean? You could evaluate
\[n! = \int_0^\infty x^ne^{-x} \ dx \]
but I am not sure how that would be easier nor whether it would avoid inspection whatever that means. I can't imagine an easier computation than multiplying $n$ numbers together.
 

topsquark

Math Team
May 2013
2,519
1,049
The Astral plane
What does "without inspection" mean? You could evaluate
\[n! = \int_0^\infty x^ne^{-x} \ dx \]
but I am not sure how that would be easier nor whether it would avoid inspection whatever that means. I can't imagine an easier computation than multiplying $n$ numbers together.
I think the OP wants the reverse... given x, solve n! = x for n.

-Dan
 

mathman

Forum Staff
May 2007
6,932
774
For small n, brute force is simplest. For large n, use Stirling's formula and invert (may not be easy).
 
May 2016
1,310
551
USA
I think the OP wants the reverse... given x, solve n! = x for n.

-Dan
Well if that is what is being asked, it sure was asked obscurely.

If we are discussing positive integers, a fairly efficient algorithm is available. To determine whether any positive integer less than 200 trillion is a factorial of an integer, a binary search against a table of the factorials of 1 through 16 will require at most 4 comparisons. The brute force involved is that of a mouse.
 
  • Like
Reactions: 1 person

SDK

Sep 2016
801
543
USA
Well if that is what is being asked, it sure was asked obscurely.

If we are discussing positive integers, a fairly efficient algorithm is available. To determine whether any positive integer less than 200 trillion is a factorial of an integer, a binary search against a table of the factorials of 1 through 16 will require at most 4 comparisons. The brute force involved is that of a mouse.
I'll agree that this was certainly not clear to me either. If this is the case, its fairly simple to get rough bounds which will make the computation fast. I'm sure someone has already thought about this and done a better job via Stirling's approximation, but a quick computation gives the following:

Notice that $\log n! = \sum_{k = 1}^n \log k$ leading to a simple integral bound
\[\int_2^n \log x \ dx \leq \log n! \leq \int_1^n \log x \ dx. \]
Solving these integrals we get the bound
\[(n-1) \log (n-1) + 1 \leq \log n! \leq n \log n.\]

Now, given an integer $m$, solve $(x-1) \log (x-1) = \log m - 1$ for $x_L$, and solve $x \log x = \log m$ for $x_R$, then if $m = n!$ for some $n$, it must be that $n \in [\exp(x_L), \exp(x_R)]$ which is easy to check. In fact, one can get an even faster computation by checking that $m$ is divisible by $\lceil x_L \rceil$ and if so, dividing it out and iterating.