58
$\begingroup$

This is an analysis question I remember thinking about in high school. Reading some of the other topics here reminded me of this, and I'd like to hear other people's solutions to this.

We have the gamma function, which has a fairly elementary form as we all know,

$\Gamma(z) = \int_0^\infty e^{-t} t^{z-1} dt = \int_0^1 \left[ \ln(t^{-1}) \right]^{z-1}$

Which satisfies of course, $\Gamma(n) = (n-1)!$, $n\in \mathbb{N}$, and the various recurrence relations and other identities that we can all look up on wikipedia or mathworld or wherever. We note that the gamma function is increasing on the interval $[a,\infty]$ where $a\approx 1.46163$.

The question is--can we come up with an explicit inverse function to the gamma function on this interval which looks similarly simple?

My techniques at the time were to write down a differential equation that the inverse would satisfy, and solve it, which I could do in terms of a power series expansion (being in high school, ignoring the issues of convergence) to get an approximate solution. But I was never able to get a very nice looking or exact solution. I have a few more sophisticated tricks now to do this, but I would be interested to see how people with more experience with these kinds of questions would go about answering this.

The gamma function also satisfies a reasonable number of somewhat interesting looking functional relations like $\Gamma(z)\Gamma(1-z)=\pi/\sin(\pi z)$. Does the inverse function satisfy any similar relations?

$\endgroup$
0

8 Answers 8

30
$\begingroup$

David Cantrell gives a good approximation of $\Gamma^{-1}(n)$ on this page.

I'll copy the result here in case that page ever goes down:

$k$ = the positive zero of the digamma function, approximately $1.461632$
$c$ = $\sqrt{2\pi}/e - \Gamma(k)$, approximately $0.036534$
$L(x)$ = $\ln(\frac{x+c}{\sqrt{2\pi}})$
$W(x)$ = Lambert W function
$ApproxInvGamma(x)$ = $L(x)/W(\frac{L(x)}{e}) + \frac{1}{2}$

$\endgroup$
12
$\begingroup$

For the benefit of generations to come I add here the python code I wrote after reading the above answers.

import numpy as np
import math
import scipy.special

def _lambert_w(z):
  """
  Lambert W function, principal branch.
  See http://en.wikipedia.org/wiki/Lambert_W_function
  Code taken from http://keithbriggs.info/software.html
  """
  eps=4.0e-16
  em1=0.3678794411714423215955237701614608
  assert z>=-em1, 'LambertW.py: bad argument %g, exiting.'%z
  if 0.0==z: 
      return 0.0
  if z<-em1+1e-4:
      q=z+em1
      r=math.sqrt(q)
      q2=q*q
      q3=q2*q
      return\
       -1.0\
       +2.331643981597124203363536062168*r\
       -1.812187885639363490240191647568*q\
       +1.936631114492359755363277457668*r*q\
       -2.353551201881614516821543561516*q2\
       +3.066858901050631912893148922704*r*q2\
       -4.175335600258177138854984177460*q3\
       +5.858023729874774148815053846119*r*q3\
       -8.401032217523977370984161688514*q3*q
  if z<1.0:
      p=math.sqrt(2.0*(2.7182818284590452353602874713526625*z+1.0))
      w=-1.0+p*(1.0+p*(-0.333333333333333333333+p*0.152777777777777777777777))
  else:
      w=math.log(z)
  if z>3.0: 
      w-=math.log(w)
  for i in xrange(10):
      e=math.exp(w)
      t=w*e-z
      p=w+1.0
      t/=e*p-0.5*(p+1.0)*t/p
      w-=t
      if abs(t)<eps*(1.0+abs(w)): 
          return w
  raise AssertionError, 'Unhandled value %1.2f'%z

def _gamma_inverse(x):
  """
  Inverse the gamma function.
  http://mathoverflow.net/questions/12828/inverse-gamma-function
  """
  k=1.461632 # the positive zero of the digamma function, scipy.special.psi
  assert x>=k, 'gamma(x) is strictly increasing for x >= k, k=%1.2f, x=%1.2f' % (k, x)
  C=math.sqrt(2*np.pi)/np.e - scipy.special.gamma(k) # approximately 0.036534
  L=np.log((x+C)/np.sqrt(2*np.pi))
  gamma_inv = 0.5+L/_lambert_w(L/np.e)
  return gamma_inv
$\endgroup$
1
10
$\begingroup$

This article addresses the question: https://www.ams.org/journals/proc/2012-140-04/S0002-9939-2011-11023-2/S0002-9939-2011-11023-2.pdf

Uchiyama, Mitsuru, The principal inverse of the gamma function, Proc. Am. Math. Soc. 140, No. 4, 1343-1348 (2012). ZBL1245.33005, MR2869117.

$\endgroup$
3
  • $\begingroup$ It works for me. $\endgroup$ Feb 25, 2017 at 5:31
  • $\begingroup$ Yeah, it was my phone, I was able to open it on my computer. $\endgroup$ Feb 27, 2017 at 5:53
  • $\begingroup$ Bibliographic info for the article: Mitsuru Uchiyama, The Principal Inverse Of The Gamma Function, Proceedings Of The American Mathematical Society, Volume 140, Number 4, April 2012, Pages 1343–1348. $\endgroup$ Aug 13, 2022 at 23:33
4
$\begingroup$

A better numerical value of the positive zero of the digamma function can be obtained by using the built-in Mathematica function FindInstance:

$k \approx 1.46163214496836234126265954233$

Then a better numerical value of $c$ is found and used:

$c=\sqrt{2\pi}/e - \Gamma(k)$

$c \approx 0.0365338144849004166003358471688$

Then the relation mentioned in other answers can be used:

$\Gamma_{approx}^{-1}(n)=L(x)/W(\frac{L(x)}{e}) + \frac{1}{2}$

However a more accurate real numerical value of the inverse gamma function is found by directly using FindInstance:

invgamnum[n_] = 
  FindInstance[Gamma[x] == n, x, Reals, WorkingPrecision -> 30]

The numerical value obtained was set to 30 decimal digits; this can be changed to an arbitrary numerical precision.

If Reals is not added in the code above, FindInstance usually yields a complex valued solution.

FindInstance can be used to find more than one solution (if they exist).

For example, for $\Gamma(x) = e$ , with Mathematica:

FindInstance[Gamma[x] == E, x, Reals, 2, WorkingPrecision -> 30]

The two numerical values obtained are:

$x=\Gamma^{-1}(e) \approx 0.328713113325854368520566502893$

$x=\Gamma^{-1}(e) \approx 3.31244088253916037027609875238$

Note that if the relation involving the Lambert W function were used, a less accurate single numerical value would be found:

$\Gamma^{-1}(e) \approx 3.3111260003863245271459515483$

$\endgroup$
3
$\begingroup$

Mathematica has an inverse gamma function. It is on the web page on special functions. This would suggest that the problem is at least simple enough for computer implementation.

I have just found more material on the inverse of the regularized incomplete gamma function from Mathematica. There are downloads on the site with information as well. Some of them are Mathematica notebooks and need the player which is free to be opened.

The information includes differential equations, representations through equivalent functions and series representations among other things.

$\endgroup$
2
  • 26
    $\begingroup$ Of course the implementation could be as simple as "solve the equation $\Gamma(z) = x$ using, e.g., Newton's method." It doesn't necessarily mean they have a good analytic understanding of the function. $\endgroup$ Jun 21, 2010 at 19:29
  • 2
    $\begingroup$ How do you get the inverse gamma function from the inverse regularized gamma function? It's not clear to me. $\endgroup$
    – Charles
    Jun 4, 2012 at 17:36
2
$\begingroup$

This should work for Mathematica:

c = 0.036534
l[x_] = Log[(x + c)/Sqrt[2*Pi]]
aig[x_] = l[x]/(ProductLog[l[x]/E]) + 1/2
$\endgroup$
2
$\begingroup$

Factorial inverse approximation is given by this formula split into couple of steps for simplicity

$$m=\frac{\ln(x)}{\ln(\ln(x)+1)} $$

$$k=\frac{\ln(\frac{m!}{x})}{\ln(m+1)}$$

$$x¡=m-k+\frac{\ln(\frac{x}{(m-k)!})}{\ln(m-k+1)}$$

Integer version

$$m=\left \lceil \frac{\ln(x)}{\ln(\ln(x)+1)} \right \rceil$$

$$k= \frac{\ln(\frac{m!}{x})}{\ln(m+1)}$$

$$x¡=\left \lfloor m-k+ \frac{\ln(\frac{x}{(m-k)!})}{\ln(m-k+1)} \right \rceil$$

(Mind the ceiling/floor marking, the last is round off, first ceiling is for better convergence only and not to have to calculate non-integer factorial twice.)

The idea is to reach $y$ from $x=y!$ as close as possible using $\frac{\ln(x)}{\ln(\ln(x)+1)}$ then, since this is undershooting, to estimate how low we are and how many times we need to multiply by $(m+1)(m+2)...(m+k)$ more, rounding this by $(m+1)^k$ since the numbers are close, finally assuming we are close enough using the estimation $(n+\epsilon)! \sim n!(n+1)^{\epsilon}$ from Gamma limit we get to the final result.

(We marked inverse factorial with inverse exclamation mark.)

The formula works for $x>1$. However, simple $\frac{(x+1)!}{x+1}=x!$ can shift it upwards.

The main advantage is that the method is giving quite a precise evaluation even for non-integer values already, certainly sufficiently for integer factorial even beyond $10^7!$. However if a better precision is needed it is sufficient to repeat the last step

$$r+\frac{\ln(\frac{x}{r!})}{\ln(r+1)}$$

It could be some special task that would require repeating this more than once, likely for small values but the step can be repeated as many times as needed.

High precision version

$$m=\frac{\ln(x)}{\ln(\ln(x)+1)} $$

$$k=\frac{\ln(\frac{m!}{x})}{\ln(m+1)}$$

$$r=m-k+\frac{\ln(\frac{x}{(m-k)!})}{\ln(m-k+\frac{1}{2})}$$

$$x¡=r+\frac{\ln(\frac{x}{r!})}{\ln(r+\frac{1}{2})}$$

Integer binary algorithm

Assume that we have integer input $x=n!$

  1. If $x=1$ return $1$
  2. Count the number of trailing zeros, $t$, in the binary representation of $x$
  3. Calculate $w=\frac{x}{t!}$
  4. Calculate the number of times $t+1$ divides $w$, rounded down to the nearest integer giving this result, but simplified and optimized for whatever programming language is used $$r= \left \lfloor \frac{\ln(w)}{\ln(t+1)} \right \rfloor$$
  5. Return $t+r$
$\endgroup$
2
  • $\begingroup$ $(3/2)! = \Gamma(5/2) = 3\sqrt{\pi}/4$. Apply your method to that, we get approx 1.484. Pretty good approximation to 1.5 ... but of course only an approximation. $\endgroup$ Jul 27, 2018 at 12:47
  • $\begingroup$ The method is designed for integer factorial evaluation. In case a better accuracy is needed for non-integer or very large integer factorial, it is sufficient to repeat the last step. It needs to be some special situation where we would need to do it more than once in general. $\endgroup$
    – user113386
    Jul 27, 2018 at 22:57
0
$\begingroup$

Here is some code I wrote for a similar problem a few years back. I used Stirling's approximation and Newton's method. It may not be the most efficient solution but it worked fine for my applications. Maybe this could help someone in the future. I would also like to emphasize that this is only an approximation and that it may be possible to get the incorrect answer if your input is sufficiently large (However I have not observed this)

Stirlings approximation: https://en.wikipedia.org/wiki/Stirling%27s_approximation

Newton's Method: https://en.wikipedia.org/wiki/Newton%27s_method

import math

q = math.log10(int(input())
def function(x):
    y = .5*math.log10(2*math.pi*x) + x*math.log10(x)-x*math.log10(math.e)-q
    return y

def derivative(x):
    y1 = ( (math.log( (1/math.e) * x) / math.log(10)) + (1/(2*math.log(10)*x)) + (1/math.log(10)))
    return y1

x0 = len(str(factorial_n))
arrX = [x0]
for i in range(0,3):
    tempx = arrX[-1]
    X_n = tempx - (function(tempx) / derivative(tempx))
    arrX.append(X_n)
print(math.floor(arrX[-1]))
$\endgroup$
1
  • $\begingroup$ This method only works for estimating the closest natural number to the inverse factorial $\endgroup$ Nov 13, 2019 at 22:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.