TOPICS
Search

Ramanujan Sequence

The Ramanujan sequence is the sequence {theta_n}_(n>=0) defined by theta_0=1/2 and, for n>=1,

theta_n=((e^n)/2-sum_(k=0)^(n-1)(n^k)/(k!))(n!)/(n^n).
(1)

Ramanujan (1911) introduced this correction in comparing e^n/2 with the partial sum of the power series for the exponential function through k=n-1. Multiplying the difference by n!/n^n expresses it in units of the next term n^n/n!. Equivalently, for n>=1, if X_n has a Poisson distribution with mean n, then

theta_n=(Pr(X_n>=n)-1/2)/(Pr(X_n=n)).
(2)

Thus theta_n measures the upper-tail excess over one half in units of the probability at the mean, a connection used to study statistical medians of Poisson distributions and gamma distributions (Alm 2003).

More precisely, let lambda_n denote the statistical median of a unit-scale gamma distribution with shape n+1. For n>=1, Choi (1994) proved the exact identity

1-theta_n=int_n^(lambda_n)(t/n)^ne^(n-t)dt.
(3)

The first few terms are

theta_0=1/2
(4)
theta_1=e/2-1
(5)
theta_2=(e^2)/4-3/2
(6)
theta_3=(e^3-17)/9
(7)
theta_4=(3e^4)/(64)-(71)/(32).
(8)

It is a decreasing sequence with limit 1/3 and satisfies 1/3<theta_n<=1/2 for n>=0 (Adell and Jodrá 2008, Bakan et al. 2016).

As n->infty, it has the divergent asymptotic expansion

theta_n∼sum_(r=0)^infty(rho_r)/(n^r)=1/3+4/(135n)-8/(2835n^2)-(16)/(8505n^3)+(8992)/(12629925n^4)+....
(9)

The coefficients can be computed directly from

rho_r=-2^rr![z^(2r+1)]{(z^2)/(2(e^z-1-z))}^(r+1),
(10)

where [z^k]f(z) denotes the coefficient of z^k in f(z) (O'Sullivan 2023). Their exponential generating function can be written implicitly as

sum_(r=0)^(infty)(rho_rx^(r+1))/((r+1)!)=ln((sinhf)/f)
(11)
x=fcothf+ln((sinhf)/f)-1,
(12)

where f is the formal power series in sqrt(x) specified by the second equation and f∼sqrt(2x). The numerators of the displayed coefficients are 1, 4, -8, -16, ... (OEIS A260306), and their denominators are 3, 135, 2835, 8505, ... (OEIS A065973).

Knuth's Ramanujan Q-function is

Q(n)=sum_(k=0)^(n-1)((n-1)!)/(n^k(n-1-k)!)
(13)
=(n!)/2(e/n)^n-theta_n.
(14)

If y(z)=ze^(y(z)), the exponential generating function of the weighted sequence {n^(n-1)Q(n)}_(n>=1) is

sum_(n=1)^inftyQ(n)n^(n-1)(z^n)/(n!)=ln1/(1-y(z)).
(15)

The function arose in Knuth's analysis of hashing with linear probing and also occurs in the birthday problem, random mapping statistics and Pollard's rho method for prime factorization, union-find algorithms under the random spanning tree model, optimum caching, and memory-conflict problems (Knuth 1985, Flajolet et al. 1995).

See also

Gamma Distribution, Incomplete Gamma Function, Poisson Distribution, Statistical Median

Explore with Wolfram|Alpha

References

Adell, J. A. and Jodrá, P. "On the Complete Monotonicity of a Ramanujan Sequence Connected with e^n." Ramanujan J. 16, 1-5, 2008. https://doi.org/10.1007/s11139-007-9088-7.Alm, S. E. "Monotonicity of the Difference Between Median and Mean of Gamma Distributions and of a Related Ramanujan Sequence." Bernoulli 9, 351-371, 2003. https://doi.org/10.3150/bj/1068128981.Bakan, A.; Ruscheweyh, S.; and Salinas, L. "More Properties of the Ramanujan Sequence." 21 Nov 2016. https://arxiv.org/abs/1605.05479.Choi, K. P. "On the Medians of Gamma Distributions and an Equation of Ramanujan." Proc. Amer. Math. Soc. 121, 245-251, 1994. https://doi.org/10.1090/S0002-9939-1994-1195477-8.Flajolet, P.; Grabner, P. J.; Kirschenhofer, P.; and Prodinger, H. "On Ramanujan's Q-Function." J. Comput. Appl. Math. 58, 103-116, 1995. https://doi.org/10.1016/0377-0427(93)E0258-N.Knuth, D. E. "An Analysis of Optimum Caching." J. Algorithms 6, 181-199, 1985. https://doi.org/10.1016/0196-6774(85)90037-9.O'Sullivan, C. "Ramanujan's Approximation to the Exponential Function and Generalizations." Ramanujan J. 62, 649-673, 2023. https://doi.org/10.1007/s11139-023-00769-3.Ramanujan, S. "Question 294." J. Indian Math. Soc. 3, 128, 1911.Sloane, N. J. A. Sequences A065973 and A260306 in "The On-Line Encyclopedia of Integer Sequences."

Cite this as:

Weisstein, Eric W. "Ramanujan Sequence." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/RamanujanSequence.html

Subject classifications