Remember Me?

 Straight Dope Message Board Remember Me?

#1
05-30-2002, 01:37 PM
 Victory Candescence Guest Join Date: Mar 2002 Location: United States Posts: 239
Math: What is the inverse of the factorial function?

For example, 2n is the inverse of log2n.

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.
__________________
"Rest assured that there is absolutely no chance of a dangerous equipment malfunction prior to your victory candescence."
#2
05-30-2002, 02:22 PM
 Newton meter Guest Join Date: Mar 2002 Location: Århus, Danmark Posts: 469
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:

Code:
```f(n,a) = { a, if n = 1
{ f(n-1, a*n), otherwise```
then fact(n) is f(n,1). Likewise:

Code:
```f-1(n,a) = { a, if n = a
{ f-1(n/a, a+1), otherwise```
gives us that fact-1(n) is f-1(n,1).

kg m²/s²

#3
05-30-2002, 02:39 PM
 rockboots Guest Join Date: May 2002 Location: El Paso Tx. Posts: 11
Do you do this 4 fun Newton meter?
#4
05-30-2002, 02:43 PM
 Newton meter Guest Join Date: Mar 2002 Location: Århus, Danmark Posts: 469
Even better, I do it for fun and get paid for it.
#5
05-30-2002, 03:21 PM
 ftg Guest Join Date: Feb 2001 Location: Not the PNW :-( Posts: 15,819
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
05-30-2002, 03:31 PM
 bonzer Guest Join Date: Jun 2001 Location: NW5 Posts: 3,040
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-ttx. 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
05-30-2002, 03:34 PM
 bonzer Guest Join Date: Jun 2001 Location: NW5 Posts: 3,040
Commonly seen integrals, not "commonly seen functions," d*mm*t. Though they are ...
#8
05-30-2002, 05:20 PM
 Newton meter Guest Join Date: Mar 2002 Location: Århus, Danmark Posts: 469
Quote:
 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.

Quote:
 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"

Quote:
 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:

Code:
`f(N) = {N+1} U f(N+1)`
and is defined by corecursion.
#9
05-30-2002, 05:49 PM
 tracer Charter Member Join Date: May 1999 Location: Silicon Valley, Cal., USA Posts: 15,785
Huh huh, you said "bijection."
#10
05-30-2002, 05:50 PM
 Newton meter Guest Join Date: Mar 2002 Location: Århus, Danmark Posts: 469
I should add that my definition of factorial also fails to halt on values outside its domain.
#11
05-30-2002, 07:09 PM
 ultrafilter Guest Join Date: May 2001 Location: In another castle Posts: 18,988
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
05-30-2002, 07:55 PM
 Newton meter Guest Join Date: Mar 2002 Location: Århus, Danmark Posts: 469
Quote:
 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.

Code:
```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:

Code:
`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
05-30-2002, 08:04 PM
 Newton meter Guest Join Date: Mar 2002 Location: Århus, Danmark Posts: 469
Oops. I should have said that double was defined corecursively. And I should have also defined it correctly:

Code:
`double(<n,S>) = <2n,double(S)>`
#14
05-30-2002, 09:04 PM
 Victory Candescence Guest Join Date: Mar 2002 Location: United States Posts: 239
Ok, so I think this should be an actual implementation in C of the function Newton Meter was talking about:

Code:
```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!
__________________
"Rest assured that there is absolutely no chance of a dangerous equipment malfunction prior to your victory candescence."
#15
05-30-2002, 09:19 PM
 Newton meter Guest Join Date: Mar 2002 Location: Århus, Danmark Posts: 469
Actually, that's what ftg suggested. What I suggested is this:

Code:
```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
05-30-2002, 09:41 PM
 ftg Guest Join Date: Feb 2001 Location: Not the PNW :-( Posts: 15,819
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
05-30-2002, 09:43 PM
 ultrafilter Guest Join Date: May 2001 Location: In another castle Posts: 18,988
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
05-31-2002, 02:17 PM
 Newton meter Guest Join Date: Mar 2002 Location: Århus, Danmark Posts: 469
Quote:
 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.
#19
05-31-2002, 04:51 PM
 Chronos Charter Member Moderator Join Date: Jan 2000 Location: The Land of Cleves Posts: 73,054
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
03-07-2013, 12:39 PM
 Veneratio Guest Join Date: Mar 2013 Posts: 2
Here ya go guys

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

Last edited by Veneratio; 03-07-2013 at 12:43 PM. Reason: Won't allow spacing so I filled in with dashes.
#21
03-07-2013, 12:54 PM
 Great Antibob Guest Join Date: Feb 2003 Posts: 4,793
Quote:
 Originally Posted by Veneratio With that being said we can create values for the inverse of Factorial by logical reasoning such that n >= 1
Hi, welcome to the SDMB.

You've produced an interesting answer, but there are definite problems with it.

1) This is an 11 year old thread. There's probably not much interest in it anymore.

2) You've defined an illegitimate inverse. The factorial is a function which maps integers to integers. As such, any potential 'inverse' function must also map integers to integers. Instead, you have a function which maps integers to rationals.

For example, you have the inverse of 5! as 2+5/6. What is (2+5/6)! ? It should produce 5, yet it doesn't, because factorials on non-integers are not well defined.

3) Even if we used the generalization of factorials to the real numbers - the Gamma function - we still have a problem. The gamma function has no inverse and can't have one.

Basically, you have a function which acts as a pseudo-inverse for those integers which are the result of a factorial. For other integers, it produces some output that is essentially arbitrary.
#22
03-07-2013, 01:06 PM
 Veneratio Guest Join Date: Mar 2013 Posts: 2
That's sort of the point though. Of course the other integers would be arbitrary, however I have defined these numbers in such a way to make the function definable, otherwise there would be no definable function. As I said in the beginning these values are based solely on logical reasoning. Basically to say that they are arbitrary. Also, it's not incredibly intelligent to say that an inverse of a function is limited to mapping in the same aspect as the function itself. It would lead to Mathematics inheriting no evolution to it's design. If we limited ourselves to certain "laws" of mathematics, we would never have calculus.

Lol also, this was the only intelligible website I found, where people actually knew what they were talking about. I just wanted to get it out there to get some feedback. Thanks!
#23
03-07-2013, 01:22 PM
 Great Antibob Guest Join Date: Feb 2003 Posts: 4,793
Quote:
 Originally Posted by Veneratio Also, it's not incredibly intelligent to say that an inverse of a function is limited to mapping in the same aspect as the function itself.
That's in the definition of an inverse. If you want to redefine it, ok, but then you're answering a different question.

There's no need to appeal to "evolution of Mathematics" (whatever that means). It's ok if you want to define your own version of an 'inverse', but it won't be the same animal.

Of course, the problem with using a home-grown version is that it doesn't behave the way the original does, which can be a problem if somebody doesn't realize it's not the same thing. That's why definitions are important and you should be careful with saying it's an 'inverse' when it doesn't have the properties we expect.

As an example, a function f has an inverse f' if and only if f(f'(n)) = f'(f(n)) = n. But in your case, this fails. If f(n) = n!, then f(f'(5)) = (2+5/6)!, which has no definition. You skirt this by defining your own "inverse", but it obviously doesn't satisfy this very basic property of traditional function inverses.

Last edited by Great Antibob; 03-07-2013 at 01:25 PM.
#24
03-07-2013, 01:50 PM
 md2000 Guest Join Date: Feb 2009 Posts: 13,238
http://en.wikipedia.org/wiki/Stirling's_approximation

For sufficiently large values of n ...
#25
03-07-2013, 01:56 PM
 CalMeacham Member Join Date: May 2000 Location: Massachusetts Posts: 41,637
Here's a paper about the inverse Gamma function:

http://www.ams.org/journals/proc/201...11-11023-2.pdf

And here are some approximations for it:

http://mathoverflow.net/questions/12...gamma-function

If you Google "Inverse Gamma Function" you'll find lots of math discussion boards talking about it.
#26
03-07-2013, 01:58 PM
 John Mace Guest Join Date: Dec 2002 Location: South Bay Posts: 81,076
Quote:
 Originally Posted by Newton meter ...not one-to-one or onto...
Oh, it's been soooo long since I heard those terms. I feel old.
#27
03-07-2013, 02:11 PM
 Great Antibob Guest Join Date: Feb 2003 Posts: 4,793
Quote:
 Originally Posted by CalMeacham Here's a paper about the inverse Gamma function: http://www.ams.org/journals/proc/201...11-11023-2.pdf
I'll add a note that even here, the inverse is limited over a range. The discontinuities ensure the general function has no inverse.

The above is probably the closest thing to an inverse of factorials, if we extend the definition of factorial over reals.

ETA: On re-reading the thread, all these points have actually been brought up before, and we're just re-hashing them again. Zombie ideas/thread, indeed.

 Bookmarks

 Thread Tools Display Modes Linear Mode

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is Off HTML code is Off Forum Rules
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home Main     About This Message Board     Comments on Cecil's Columns/Staff Reports     General Questions     Great Debates     Elections     Cafe Society     The Game Room     Thread Games     In My Humble Opinion (IMHO)     Mundane Pointless Stuff I Must Share (MPSIMS)     Marketplace     The BBQ Pit

All times are GMT -5. The time now is 11:14 AM.

 -- Straight Dope v3.7.3 -- Sultantheme's Responsive vB3-blue Contact Us - Straight Dope Homepage - Archive - Top