# Math: What is the inverse of the factorial function? **URL:** \ **Category:** Factual Questions\ **Created:** [May 30, 2002, 5:37pm UTC](https://boards.straightdope.com/t/math-what-is-the-inverse-of-the-factorial-function/111576 "2002-05-30T17:37:53Z")\ **Posts on this page:** 20\ **Page:** 1
**Author:** ![Victory\_Candescence](https://avatars.discourse-cdn.com/v4/letter/v/e5b9ba/32.png) [@Victory\_Candescence](https://boards.straightdope.com/u/Victory_Candescence)\ **Post date:** [May 30, 2002, 5:37pm UTC](https://boards.straightdope.com/t/math-what-is-the-inverse-of-the-factorial-function/111576/1 "2002-05-30T17:37:53Z")
For example, 2[sup]n[/sup] is the inverse of log[sub]2[/sub]n. Or, you could answer my post by answering the question “What’s the inverse of the Gamma Function?”, since it seems to basically be the same as factorial, and has the advantage of applying to non-integers. ---
**Author:** ![Newton\_meter](https://avatars.discourse-cdn.com/v4/letter/n/57b2e6/32.png) [@Newton\_meter](https://boards.straightdope.com/u/Newton_meter)\ **Post date:** [May 30, 2002, 6:22pm UTC](https://boards.straightdope.com/t/math-what-is-the-inverse-of-the-factorial-function/111576/2 "2002-05-30T18:22:43Z")
It’s the function that maps n! to n. But I suppose that’s probably not what you’re looking for. The factorial function doesn’t have an inverse over the intgers, since it (factorial) is not one-to-one or onto the integers (remember that 0! and 1! are both 1). Your inverse function would have a subset of the positive integers as its domain. If you took a linear recursive algorithm for factorial, it is easy to see how to invert it. For instance, if I defined: ```auto f(n,a) = { a, if n = 1 { f(n-1, a*n), otherwise ``` then fact(n) is f(n,1). Likewise: ```auto f[sup]-1[/sup](n,a) = { a, if n = a { f[sup]-1[/sup](n/a, a+1), otherwise ``` gives us that fact[sup]-1/sup is f[sup]-1/sup. kg m²/s² PS: Given your sig, your name should be **Corecursion**. ---
**Author:** ![rockboots](https://avatars.discourse-cdn.com/v4/letter/r/ecccb3/32.png) [@rockboots](https://boards.straightdope.com/u/rockboots)\ **Post date:** [May 30, 2002, 6:39pm UTC](https://boards.straightdope.com/t/math-what-is-the-inverse-of-the-factorial-function/111576/3 "2002-05-30T18:39:35Z")
Do you do this 4 fun Newton meter? ---
**Author:** ![Newton\_meter](https://avatars.discourse-cdn.com/v4/letter/n/57b2e6/32.png) [@Newton\_meter](https://boards.straightdope.com/u/Newton_meter)\ **Post date:** [May 30, 2002, 6:43pm UTC](https://boards.straightdope.com/t/math-what-is-the-inverse-of-the-factorial-function/111576/4 "2002-05-30T18:43:00Z")
Even better, I do it for fun and get paid for it. ---
**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\ **Post date:** [May 30, 2002, 7:21pm UTC](https://boards.straightdope.com/t/math-what-is-the-inverse-of-the-factorial-function/111576/5 "2002-05-30T19:21:18Z")
**Newton Meter** ’s little function only halts when fed a factorial value (e.g., halts on 24 but not 25). It is really of no value. (You can just compute factorials till you get to your input then output the index.) I don’t understand why it was posted. In terms of order of growth, using Sterling’s formula, you can see the inverse is about log x/log log x + low order terms. Also, “corecursion” requires at least _two_ functions, so that part misses too. ---
**Author:** ![bonzer](https://avatars.discourse-cdn.com/v4/letter/b/45deac/32.png) [@bonzer](https://boards.straightdope.com/u/bonzer)\ **Post date:** [May 30, 2002, 7:31pm UTC](https://boards.straightdope.com/t/math-what-is-the-inverse-of-the-factorial-function/111576/6 "2002-05-30T19:31:19Z")
FWIW, I can’t remember ever coming across an occasion where I or anyone else had to worry about the inverse of a Gamma function. Furthermore - and here I’m really sticking my neck out for someone to trot out a counterexample - that’d be true of virtually any of the standard special functions. Why? I think it’s possibly to do with the fact that they usually derive from integrals. While thinking of it as a generalisation of _n!_ is very nice, in practice you’ll probably come across it at least as often as some variation on the integral of _e[sup]-t[/sup]t[sup]x[/sup]_. And that’s even more true of the other special functions. (_log(x)_ and the trig functions are the exceptions here.) They’re cases where people have found it useful to define functions for commonly seen functions, not functions that have commonly needed inverses. **rockboots** , what would you expect someone with a username **Newton meter** to do for fun? ---
**Author:** ![bonzer](https://avatars.discourse-cdn.com/v4/letter/b/45deac/32.png) [@bonzer](https://boards.straightdope.com/u/bonzer)\ **Post date:** [May 30, 2002, 7:34pm UTC](https://boards.straightdope.com/t/math-what-is-the-inverse-of-the-factorial-function/111576/7 "2002-05-30T19:34:49Z")
Commonly seen _integrals_, not “commonly seen functions,” d_mm_t. Though they are … ---
**Author:** ![Newton\_meter](https://avatars.discourse-cdn.com/v4/letter/n/57b2e6/32.png) [@Newton\_meter](https://boards.straightdope.com/u/Newton_meter)\ **Post date:** [May 30, 2002, 9:20pm UTC](https://boards.straightdope.com/t/math-what-is-the-inverse-of-the-factorial-function/111576/8 "2002-05-30T21:20:39Z")
> [@](#): > > \*Originally posted by ftg \* > **Newton Meter’s little function only halts when fed a factorial value (e.g., halts on 24 but not 25).** Of course. I make no claims for what my functions do with values outside their domain. What else would you expect? In order to invert any function, it has to be a bijection. Factorial can be cast as a bijection between the positive integers and the image of the positive integers under the factorial function (trivially onto, provably one-to-one). Thus, the inverse function maps the “factorials” to the positive integers. If one were interested in computing the function, it would be a trivial matter to make it halt for all values (hint, what should happen when n\<1), but I’m just not sure what you want to return in that case, so I left it undefined. > [@](#): > > **It is really of no value. (You can just compute factorials till you get to your input then output the index.) I don’t understand why it was posted.** Hopefully it is of _some_ value: 1. It directly answers the question, which noone had yet done to that point 2. It provides an “interesting” algorithm to compute the function 3. It demonstrates an algorithm that was reached by a transforming the original, rather than “thinking” > [@](#): > > **Also, “corecursion” requires at least _two_ functions, so that part misses too.** I think you are confusing _mutual recursion_ with corecursion. The following function from integers to sets of integers takes an integer and produces the set of all integers greater than that number: ```auto f(N) = {N+1} U f(N+1) ``` and is defined by corecursion. ---
**Author:** ![tracer](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/tracer/32/20578_2.png) [@tracer](https://boards.straightdope.com/u/tracer)\ **Post date:** [May 30, 2002, 9:49pm UTC](https://boards.straightdope.com/t/math-what-is-the-inverse-of-the-factorial-function/111576/9 "2002-05-30T21:49:34Z")
Huh huh, you said “bijection.” ---
**Author:** ![Newton\_meter](https://avatars.discourse-cdn.com/v4/letter/n/57b2e6/32.png) [@Newton\_meter](https://boards.straightdope.com/u/Newton_meter)\ **Post date:** [May 30, 2002, 9:50pm UTC](https://boards.straightdope.com/t/math-what-is-the-inverse-of-the-factorial-function/111576/10 "2002-05-30T21:50:02Z")
I should add that my definition of factorial also fails to halt on values outside its domain. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [May 30, 2002, 11:09pm UTC](https://boards.straightdope.com/t/math-what-is-the-inverse-of-the-factorial-function/111576/11 "2002-05-30T23:09:34Z")
[This site](http://documents.wolfram.com/v4/RefGuide/InverseGammaReg.html) has a link (the one that says “Section 3.2.10.”) which might describe the inverse of a gamma function (the incomplete regularized gamma function, to be precise). I couldn’t get the page to load, so it’s probably pretty image heavy, but it might have some answers. There will be no inverse to the gamma function proper. It’s not one-to-one on the negative reals, and it’s non-zero everywhere. Nevertheless, you might be able to find an inverse if you restrict the argument to be real and not less than two. Just for my information, what are corecursion and mutual recursion? ---
**Author:** ![Newton\_meter](https://avatars.discourse-cdn.com/v4/letter/n/57b2e6/32.png) [@Newton\_meter](https://boards.straightdope.com/u/Newton_meter)\ **Post date:** [May 30, 2002, 11:55pm UTC](https://boards.straightdope.com/t/math-what-is-the-inverse-of-the-factorial-function/111576/12 "2002-05-30T23:55:32Z")
> [@](#): > > \*Originally posted by ultrafilter \* > **Just for my information, what are corecursion and mutual recursion?** Mutual recursion is pretty common. Two or more functions are defined in terms of each other. ```auto even(n) = { true, if n = 0 { odd(n-1), otherwise odd(n) = { false, if n = 0 { even(n-1), otherwise ``` Corecursion is pretty hard to describe, and I’m not sure anyone has ever come up with a simple definition (we know it when we see it :)). The book _Vicious Circles_ by Jon Barwise and Larry Moss contains a good introduction, but it requires that quite a bit of detail be waded through first. Corecursion is the formal dual of recursion. It’s easiest (though not exactly accurate) to think of corecursion as “like recursion” but without a base case to guarantee it stops. The following function takes a stream of numbers (a pair of a number and a stream), and produces a stream of their doubles: ```auto double() = ``` A common problem with beginners in Computer Science classes is they accidentally write an infinite loop. Corecursive functions are _supposed_ to produce infinite output (sometimes), which is actually OK if you never try to take all the output at the same time. A joke among the eggheads I went to graduate school with was, when we were grading student projects, we would call an infinite loop a “corecursive algorithm”. ---
**Author:** ![Newton\_meter](https://avatars.discourse-cdn.com/v4/letter/n/57b2e6/32.png) [@Newton\_meter](https://boards.straightdope.com/u/Newton_meter)\ **Post date:** [May 31, 2002, 12:04am UTC](https://boards.straightdope.com/t/math-what-is-the-inverse-of-the-factorial-function/111576/13 "2002-05-31T00:04:39Z")
Oops. I _should_ have said that double was defined corecursively. And I _should_ have also defined it correctly: ```auto double() = <2n,double(S)> ``` ---
**Author:** ![Victory\_Candescence](https://avatars.discourse-cdn.com/v4/letter/v/e5b9ba/32.png) [@Victory\_Candescence](https://boards.straightdope.com/u/Victory_Candescence)\ **Post date:** [May 31, 2002, 1:04am UTC](https://boards.straightdope.com/t/math-what-is-the-inverse-of-the-factorial-function/111576/14 "2002-05-31T01:04:18Z")
Ok, so I think this should be an actual implementation in C of the function **Newton Meter** was talking about: ```auto int unfactorial(long x) { long factorial = 1; for(int i = 1; i < MAXINT; ++i) { factorial *= i; if( factorial >= x) return i; } return MAXINT; } ``` The only difference is that it halts for all input, taking the first number that produces a factorial bigger than the input. I don’t like functions to go into infinite loops for any input. Thanks to everyone for showing me the obvious: just calculate factorials until you hit the input that gets the number you’re looking for. And… hey, I found out what corecursion is! Two answers for the price of one! ---
**Author:** ![Newton\_meter](https://avatars.discourse-cdn.com/v4/letter/n/57b2e6/32.png) [@Newton\_meter](https://boards.straightdope.com/u/Newton_meter)\ **Post date:** [May 31, 2002, 1:19am UTC](https://boards.straightdope.com/t/math-what-is-the-inverse-of-the-factorial-function/111576/15 "2002-05-31T01:19:35Z")
Actually, that’s what **ftg** suggested. What I suggested is this: ```auto int unfactorial(int n) { int a; for (a = 1; n != a; ++a) n = n/a; return a; } ``` which also halts on all inputs (due to integer division). ---
**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\ **Post date:** [May 31, 2002, 1:41am UTC](https://boards.straightdope.com/t/math-what-is-the-inverse-of-the-factorial-function/111576/16 "2002-05-31T01:41:11Z")
Sorry, in advance, for continuing the “recursive” side discussion. In computer science, “recursive” has two distinct common meanings. First is the usual “subroutine that calls itself (directly or indirectly)”. The second is in an area dear to my heart, Theory of Computation\*, where it means “computable by a Turing Machine that always halts.” (Note that it is impossible to give a purely syntactic specification of this meaning of “recursive”.) The point being, that a meaning has a context. Since **Recursion** ’s sig used code, I assumed the first context. Since **Newton meter** also used code (there are programming langs. that allow similar style defs.), I again assumed the same context. In programming world, “corecursion” is used in contexts such as “coroutines” when two subroutines call each other (with “call” even being liberally used here). Of course it can easily have other meanings in other contexts, just like “recursive” does. I was not psychic enough to divine **Newton meter** ’s context. \*Which I _used_ to get paid for teaching. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [May 31, 2002, 1:43am UTC](https://boards.straightdope.com/t/math-what-is-the-inverse-of-the-factorial-function/111576/17 "2002-05-31T01:43:57Z")
All right, mutual recursion is what I thought it is. Corecursion is something I’ve seen before, although I think y’all are using a different framework for recursive functions from the one I’m familiar with. _Vicious Circles_ is a book I’ve been meaning to look at for some time; I guess I’ve got another reason now. Thanks much! ---
**Author:** ![Newton\_meter](https://avatars.discourse-cdn.com/v4/letter/n/57b2e6/32.png) [@Newton\_meter](https://boards.straightdope.com/u/Newton_meter)\ **Post date:** [May 31, 2002, 6:17pm UTC](https://boards.straightdope.com/t/math-what-is-the-inverse-of-the-factorial-function/111576/18 "2002-05-31T18:17:57Z")
> [@](#): > > \*Originally posted by ftg \* > **Sorry, in advance, for continuing the “recursive” side discussion.** You’re certainly right that “recursive” is overloaded, and that **Recursive** ’s old sig was recursive in a commonly used sense. My joke was a little too obscure, and for that _I_ should be the one apologizing, not you. ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [May 31, 2002, 8:51pm UTC](https://boards.straightdope.com/t/math-what-is-the-inverse-of-the-factorial-function/111576/19 "2002-05-31T20:51:01Z")
And here, I thought that you meant **Recursive** ’s new sigline, which is “Tacky sigline.”. Although that’s really more self-referential than recursive. ---
**Author:** ![Veneratio](https://avatars.discourse-cdn.com/v4/letter/v/f9ae1b/32.png) [@Veneratio](https://boards.straightdope.com/u/Veneratio)\ **Post date:** [March 7, 2013, 5:39pm UTC](https://boards.straightdope.com/t/math-what-is-the-inverse-of-the-factorial-function/111576/20 "2013-03-07T17:39:01Z")
Say for instance we have a defined function called Beta such that B(b,t,v,n) can take any base 10 value (v) and convert it to any base (b) you please but only outputting a specified period (t). Such function would be: --------------- / v - v mod (b^((t-1)-((n-1) mod t)) B(b,t,v,n) = | ------------------------------------------- | mod b --------------- -------- b^((t-1)-((n-1) mod t) ------/ With that being said we can create values for the inverse of Factorial by logical reasoning such that n \>= 1 n | n! | n!^(-1) 1 | 1 | 1 2 | 2 | 2 3 | 6 | 2 3/6 4 | 24 | 2 4/6 5 | 120| 2 5/6 6 | | 3 7 | | 3 7/24 8 | | 3 8/24 9 | | 3 9/24 10| | 3 10/24 11| | 3 11/24 12| | 3 12/24 13| | 3 13/24 14| | 3 14/24 15| | 3 15/24 16| | 3 16/24 17| | 3 17/24 18| | 3 18/24 19| | 3 19/24 20| | 3 20/24 21| | 3 21/24 22| | 3 22/24 23| | 3 23/24 24| | 4 … And so on so forth By analyzing the number set you can see that the numbers go in order of the previous factorial index plus n/(the next factorial index). Removing the Fractions shows a pattern. And by taking the difference of this pattern we can then use our now defined Beta function to find the equation. Our final function looks like: n!^(-1) = f(n-1) + n / [( f(n-1)+1)!], such that f(0) = 0 n | f(n) | f(n) - f(n-1) 1 | 1 | 1 2 | 2 | 1 3 | 2 | 0 4 | 2 | 0 5 | 2 | 0 6 | 3 | 1 7 | 3 | 0 8 | 3 | 0 9 | 3 | 0 10| 3 | 0 11| 3 | 0 12| 3 | 0 13| 3 | 0 14| 3 | 0 15| 3 | 0 16| 3 | 0 17| 3 | 0 18| 3 | 0 19| 3 | 0 20| 3 | 0 21| 3 | 0 22| 3 | 0 23| 3 | 0 24| 4 | 1 This gives us a function that looks like this. --------------------------- /----------- f(n-1)------ f(n) = sigma(i=1 to n, | B(2, i, --------------, i) | ------------------------------------ [f(n-1)+1]! —/ There ya go guys have fun!!! [Next page](https://boards.straightdope.com/t/math-what-is-the-inverse-of-the-factorial-function/111576.md?page=2)