Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)?

share|improve this question
1  
Which interests you more: a closed form for $x$, or a practical algorithm for computing $x$? –  user2357112 May 17 at 6:54
4  
To unfactorilize, use exact forms of Stirling equivalilent. –  Did May 17 at 7:09
1  
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
add comment

2 Answers 2

up vote 7 down vote accepted

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.

share|improve this answer
3  
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
add comment

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.

share|improve this answer
    
@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
3  
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
1  
@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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.