The Straight Dope

Go Back   Straight Dope Message Board > Main > General Questions

Reply
 
Thread Tools Display Modes
  #1  
Old 05-30-2002, 12:37 PM
Victory Candescence Victory Candescence is offline
Guest
 
Join Date: Mar 2002
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."
Reply With Quote
Advertisements  
  #2  
Old 05-30-2002, 01:22 PM
Newton meter Newton meter is offline
Guest
 
Join Date: Mar 2002
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

PS: Given your sig, your name should be Corecursion.
Reply With Quote
  #3  
Old 05-30-2002, 01:39 PM
rockboots rockboots is offline
Guest
 
Join Date: May 2002
Do you do this 4 fun Newton meter?
Reply With Quote
  #4  
Old 05-30-2002, 01:43 PM
Newton meter Newton meter is offline
Guest
 
Join Date: Mar 2002
Even better, I do it for fun and get paid for it.
Reply With Quote
  #5  
Old 05-30-2002, 02:21 PM
ftg ftg is offline
Guest
 
Join Date: Feb 2001
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.
Reply With Quote
  #6  
Old 05-30-2002, 02:31 PM
bonzer bonzer is offline
Guest
 
Join Date: Jun 2001
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?
Reply With Quote
  #7  
Old 05-30-2002, 02:34 PM
bonzer bonzer is offline
Guest
 
Join Date: Jun 2001
Commonly seen integrals, not "commonly seen functions," d*mm*t. Though they are ...
Reply With Quote
  #8  
Old 05-30-2002, 04:20 PM
Newton meter Newton meter is offline
Guest
 
Join Date: Mar 2002
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.
Reply With Quote
  #9  
Old 05-30-2002, 04:49 PM
tracer tracer is offline
Charter Member
 
Join Date: May 1999
Location: Silicon Valley, Cal., USA
Posts: 15,563
Huh huh, you said "bijection."
Reply With Quote
  #10  
Old 05-30-2002, 04:50 PM
Newton meter Newton meter is offline
Guest
 
Join Date: Mar 2002
I should add that my definition of factorial also fails to halt on values outside its domain.
Reply With Quote
  #11  
Old 05-30-2002, 06:09 PM
ultrafilter ultrafilter is offline
Guest
 
Join Date: May 2001
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?
Reply With Quote
  #12  
Old 05-30-2002, 06:55 PM
Newton meter Newton meter is offline
Guest
 
Join Date: Mar 2002
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".
Reply With Quote
  #13  
Old 05-30-2002, 07:04 PM
Newton meter Newton meter is offline
Guest
 
Join Date: Mar 2002
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)>
Reply With Quote
  #14  
Old 05-30-2002, 08:04 PM
Victory Candescence Victory Candescence is offline
Guest
 
Join Date: Mar 2002
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."
Reply With Quote
  #15  
Old 05-30-2002, 08:19 PM
Newton meter Newton meter is offline
Guest
 
Join Date: Mar 2002
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).
Reply With Quote
  #16  
Old 05-30-2002, 08:41 PM
ftg ftg is offline
Guest
 
Join Date: Feb 2001
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.
Reply With Quote
  #17  
Old 05-30-2002, 08:43 PM
ultrafilter ultrafilter is offline
Guest
 
Join Date: May 2001
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!
Reply With Quote
  #18  
Old 05-31-2002, 01:17 PM
Newton meter Newton meter is offline
Guest
 
Join Date: Mar 2002
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.
Reply With Quote
  #19  
Old 05-31-2002, 03:51 PM
Chronos Chronos is offline
Charter Member
 
Join Date: Jan 2000
Location: The Land of Cleves
Posts: 54,920
And here, I thought that you meant Recursive's new sigline, which is "Tacky sigline.". Although that's really more self-referential than recursive.
Reply With Quote
  #20  
Old 03-07-2013, 11:39 AM
Veneratio Veneratio is offline
Guest
 
Join Date: Mar 2013
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 11:43 AM.. Reason: Won't allow spacing so I filled in with dashes.
Reply With Quote
  #21  
Old 03-07-2013, 11:54 AM
Great Antibob Great Antibob is offline
Guest
 
Join Date: Feb 2003
Quote:
Originally Posted by Veneratio View Post
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.
Reply With Quote
  #22  
Old 03-07-2013, 12:06 PM
Veneratio Veneratio is offline
Guest
 
Join Date: Mar 2013
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!
Reply With Quote
  #23  
Old 03-07-2013, 12:22 PM
Great Antibob Great Antibob is offline
Guest
 
Join Date: Feb 2003
Quote:
Originally Posted by Veneratio View Post
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 12:25 PM..
Reply With Quote
  #24  
Old 03-07-2013, 12:50 PM
md2000 md2000 is offline
Guest
 
Join Date: Feb 2009
http://en.wikipedia.org/wiki/Stirling's_approximation

For sufficiently large values of n ...
Reply With Quote
  #25  
Old 03-07-2013, 12:56 PM
CalMeacham CalMeacham is online now
Guest
 
Join Date: May 2000
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.
Reply With Quote
  #26  
Old 03-07-2013, 12:58 PM
John Mace John Mace is offline
Guest
 
Join Date: Dec 2002
Quote:
Originally Posted by Newton meter View Post
...not one-to-one or onto...
Oh, it's been soooo long since I heard those terms. I feel old.
Reply With Quote
  #27  
Old 03-07-2013, 01:11 PM
Great Antibob Great Antibob is offline
Guest
 
Join Date: Feb 2003
Quote:
Originally Posted by CalMeacham View Post
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.
Reply With Quote
Reply



Bookmarks

Thread Tools
Display Modes

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 Jump


All times are GMT -5. The time now is 06:56 PM.


Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2014, vBulletin Solutions, Inc.

Send questions for Cecil Adams to: cecil@chicagoreader.com

Send comments about this website to: webmaster@straightdope.com

Terms of Use / Privacy Policy

Advertise on the Straight Dope!
(Your direct line to thousands of the smartest, hippest people on the planet, plus a few total dipsticks.)

Publishers - interested in subscribing to the Straight Dope?
Write to: sdsubscriptions@chicagoreader.com.

Copyright 2013 Sun-Times Media, LLC.