Golomb–Dickman constant

From Wikipedia, the free encyclopedia

(Redirected from 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.$

Let a_n 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, $λ n$ is 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 $λ 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 $λ$ . 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.

There are several expressions for $λ$ . 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 $ρ(t)$ is the Dickman function.

A related result is the one hundred prisoners problem in random permutation statistics: asymptotically, the fraction of permutations with a cycle of length greater than n/2 is $\log 2 \approx 0.693$ , or about 69%.

[edit] See also

[edit] External links

Weisstein, Eric W., "Golomb-Dickman Constant" from MathWorld.
Sloane's A084945 . The On-Line Encyclopedia of Integer Sequences (external link). AT&T Labs Research.
Finch, Steven R. (2003). Mathematical Constants. Cambridge University Press. pp. 284–286. ISBN 0521818052. http://books.google.com/books?id=DL5iVYNoEa0C.

Golomb–Dickman constant

From Wikipedia, the free encyclopedia

[edit] See also

[edit] External links

Views

Personal tools

Navigation

Search

Interaction

Toolbox

Languages