#1




Math: What is the inverse of the factorial function?
For example, 2^{n} is the inverse of log_{2}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 nonintegers.
__________________
"Rest assured that there is absolutely no chance of a dangerous equipment malfunction prior to your victory candescence." 
Advertisements  


#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 onetoone 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(n1, a*n), otherwise Code:
f^{1}(n,a) = { a, if n = a { f^{1}(n/a, a+1), otherwise 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^{t}t^{x}. 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," d*mm*t. Though they are ...

#8




Quote:
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 onetoone). 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:
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:
Code:
f(N) = {N+1} U f(N+1) 
#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 onetoone on the negative reals, and it's nonzero 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




Quote:
Code:
even(n) = { true, if n = 0 { odd(n1), otherwise odd(n) = { false, if n = 0 { even(n1), otherwise 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)> 
#13




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




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; } 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




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; } 
#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




Quote:

#19




And here, I thought that you meant Recursive's new sigline, which is "Tacky sigline.". Although that's really more selfreferential than recursive.

#20




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^((t1)((n1) mod t)) \ B(b,t,v,n) =    mod b  \ b^((t1)((n1) 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(n1) + n / [ ( f(n1)+1)!], such that f(0) = 0 n  f(n)  f(n)  f(n1) 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(n1) \ f(n) = sigma(i=1 to n,  B(2, i, , i)  \ [f(n1)+1]! / There ya go guys have fun!!! Last edited by Veneratio; 03072013 at 12:43 PM.. Reason: Won't allow spacing so I filled in with dashes. 
#21




Quote:
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 nonintegers 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 pseudoinverse for those integers which are the result of a factorial. For other integers, it produces some output that is essentially arbitrary. 
#22




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




Quote:
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 homegrown 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; 03072013 at 01:25 PM.. 
#24




#25




Here's a paper about the inverse Gamma function:
http://www.ams.org/journals/proc/201...11110232.pdf And here are some approximations for it: http://mathoverflow.net/questions/12...gammafunction If you Google "Inverse Gamma Function" you'll find lots of math discussion boards talking about it. 
#26




Oh, it's been soooo long since I heard those terms. I feel old.

#27




Quote:
The above is probably the closest thing to an inverse of factorials, if we extend the definition of factorial over reals. ETA: On rereading the thread, all these points have actually been brought up before, and we're just rehashing them again. Zombie ideas/thread, indeed. 
Bookmarks 
Thread Tools  
Display Modes  

