# How can I unfactorilize number?

Consider the equation

$x! = y$

Say we know $y$ and were trying to find $x$:

What method could I use to get $x$ (e.g. a closed formula)?

-
Which interests you more: a closed form for $x$, or a practical algorithm for computing $x$? –  user2357112 May 17 at 6:54
To unfactorilize, use exact forms of Stirling equivalilent. –  Did May 17 at 7:09
Assuming you know beforehand that such an $x\in\mathbb Z$ exists, I imagine that there is probably some simple bound on the number of digits in $n!$ and with the exception of the trivial small cases, this number should uniquely identify the factorial. If the bound was weak then you wouldn't get a closed formula, but you could just divide by the candidates and take the last one that gives you an integer; still probably faster than dividing by all of the numbers. –  Eric Stucky May 17 at 7:21

The factorial function is a special case of the Gamma function, which satisfies for positive integers $n$ $$\Gamma(n) = (n-1)!,$$ so what you really want is an inverse to this function. In general the inverse is not simple, but this has been discussed here.

-
Hmmm...is $\Gamma$ injective on $\mathbb R$? I don't think so. But it is injective on $[k,\infty)$ for sufficiently large $k$ (say, $k\geq 1$). –  MPW May 17 at 6:49
You are right! Thank you, I'll edit that :) –  user139388 May 17 at 6:50

Are you insisting that solutions be integer? If so, start by dividing $y$ by $2$, then the quotient by $3$, then the quotient of that by $4$, and so on. If you reach $1$, there is a solution and the last number you divided by is $x$. If you reach smaller than $1$ before reaching $1$, there is no integer solution.

-
@Thomas I was trying to think of a way to do it faster asymptotically. I think you should post your binary search approach as an answer. –  Goos May 17 at 15:03
Actually faster than this would be to multiply up from $1$ now that I think about it, since multiplication is slightly faster than division. @Thomas Factoring in computational complexity, is that sure? Computing a particular $k!$ does take some time, and a binary search would have you computing at least one $k!$ that is greater than $y$. This approach essentially does that too. So unless there is some fast way to compute a $k!$ (akin to repeated squaring for raising to powers) then do you still hold that a binary search would be faster? –  alex.jordan May 17 at 18:44
@alex.jordan No, my idea was to e.g. given $200!$, you would first quickly work out a generous upper bound on $k$ (perhaps a fast version of Stirling's, say $(1, 400)$), sieving a few primes in that interval, and then checking if $200!$ (which is given) is a multiple of $211$, if not, is a multiple of $101$, if it does, what about $157$, and so on, until you locate $k$ (using primes for the search predicate to hold). Of course this approach is reliable only if the input actually is a factorial! It would take some analysis to work out if it really is faster, though, I think so for large $k$. –  Thomas May 18 at 0:09
@Thomas And so what if 211 does not divide $y$, but 199, the next smaller prime does? Exactly how are you going to find $x$? Even assuming that $y$ is of the form $k!$ in the first place, how are you going to determine if $x$ is $199$, $200$, ..., or $210$? At some point you will have to compute a factorial number, and you've saved no time. –  alex.jordan May 18 at 0:39
@alex.jordan That is correct, I was about to post a comment. The binary search approach needs some setup and requires much less divisions, but only tells you $k$ is between two consecutive primes, and I don't know of a fast way of working out which one in the interval it is. I'll delete my first comment, ah well, it was a good attempt. Still I wouldn't consider implementing it in another way than your answer for practical purposes, since ultimately $k$ is bounded by available memory! –  Thomas May 18 at 0:45