Math: What is the inverse of the factorial function?

Factual Questions
1

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.

2

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:


f(n,a) = { a, if n = 1
         { f(n-1, a*n), otherwise

then fact(n) is f(n,1). Likewise:


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.

3

Do you do this 4 fun Newton meter?

4

Even better, I do it for fun and get paid for it.

5

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.

6

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?

7

Commonly seen integrals, not “commonly seen functions,” dmmt. Though they are …

8

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.

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”

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:


f(N) = {N+1} U f(N+1)

and is defined by corecursion.

9

Huh huh, you said “bijection.”

10

I should add that my definition of factorial also fails to halt on values outside its domain.

11

This site 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?

12

Mutual recursion is pretty common. Two or more functions are defined in terms of each other.


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:


double(<n,S>) = <n,double(S)>

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”.

13

Oops. I should have said that double was defined corecursively. And I should have also defined it correctly:


double(<n,S>) = <2n,double(S)>
14

Ok, so I think this should be an actual implementation in C of the function Newton Meter was talking about:



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!

15

Actually, that’s what ftg suggested. What I suggested is this:


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

16

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.

17

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!

18

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.

19

And here, I thought that you meant Recursive’s new sigline, which is “Tacky sigline.”. Although that’s really more self-referential than recursive.

20

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!!!