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)?
$\begingroup$
$\endgroup$
3
-
1$\begingroup$ Which interests you more: a closed form for $x$, or a practical algorithm for computing $x$? $\endgroup$ – user2357112 supports Monica May 17 '14 at 6:54
-
4$\begingroup$ To unfactorilize, use exact forms of Stirling equivalilent. $\endgroup$ – Did May 17 '14 at 7:09
-
1$\begingroup$ 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. $\endgroup$ – Eric Stucky May 17 '14 at 7:21
Add a comment
|
$\begingroup$
$\endgroup$
2
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.
-
3$\begingroup$ 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$). $\endgroup$ – MPW May 17 '14 at 6:49
-
$\begingroup$ You are right! Thank you, I'll edit that :) $\endgroup$ – user139388 May 17 '14 at 6:50
$\begingroup$
$\endgroup$
5
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.
answered May 17 '14 at 6:00
-
$\begingroup$ @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. $\endgroup$ – 6005 May 17 '14 at 15:03
-
3$\begingroup$ 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? $\endgroup$ – alex.jordan May 17 '14 at 18:44
-
$\begingroup$ @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$. $\endgroup$ – Thomas May 18 '14 at 0:09
-
1$\begingroup$ @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. $\endgroup$ – alex.jordan May 18 '14 at 0:39
-
$\begingroup$ @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! $\endgroup$ – Thomas May 18 '14 at 0:45
