Golomb–Dickman constant

In mathematics, the Golomb–Dickman constant arises in the theory of random permutations and in number theory. Its value is

\lambda = 0.62432 99885 43550 87099 29363 83100 83724\dots.

Definitions

Let an be the average — taken over all permutations of a set of size n — of the length of the longest cycle in each permutation. Then the Golomb–Dickman constant is

\lambda = \lim_{n\to\infty} \frac{a_n}{n}.

In the language of probability theory, \lambda n is asymptotically the expected length of the longest cycle in a uniformly distributed random permutation of a set of size n.

In number theory, the Golomb–Dickman constant appears in connection with the average size of the largest prime factor of an integer. More precisely,

\lambda = \lim_{n\to\infty} \frac1n \sum_{k=2}^n \frac{\log(P_1(k))}{\log(k)},

where P_1(k) is the largest prime factor of k. So if k is a d digit integer, then \lambda d is the asymptotic average number of digits of the largest prime factor of k.

The Golomb–Dickman constant appears in number theory in a different way. What is the probability that second largest prime factor of n is smaller than the square root of the largest prime factor of n? Asymptotically, this probability is \lambda. More precisely,

\lambda = \lim_{n\to\infty} \text{Prob}\left\{P_2(n) \le \sqrt{P_1(n)}\right\}

where P_2(n) is the second largest prime factor n.

Formulas

There are several expressions for \lambda. Namely,

\lambda = \int_0^\infty e^{-t - E_1(t)} dt

where E_1(t) is the exponential integral,

\lambda = \int_0^\infty \frac{\rho(t)}{t+2} dt

and

\lambda = \int_0^\infty \frac{\rho(t)}{(t+1)^2} dt

where \rho(t) is the Dickman function.

See also

External links

This article is issued from Wikipedia - version of the Sunday, March 27, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.