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$

It is not known whether this constant is rational or irrational.

Definitions

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_ \frac.$

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_ \frac1n \sum_^n \frac,$
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_ \text\left\$
where $P_2(n)$ is the second largest prime factor ''n''.

The Golomb-Dickman constant also arises when we consider the average length of the largest cycle of any function from a finite set to itself. If ''X'' is a finite set, if we repeatedly apply a function ''f'': ''X'' → ''X'' to any element ''x'' of this set, it eventually enters a cycle, meaning that for some ''k'' we have $f^(x) = f^n(x)$ for sufficiently large ''n''; the smallest ''k'' with this property is the length of the cycle. Let ''b''_''n'' be the average, taken over all functions from a set of size ''n'' to itself, of the length of the largest cycle. Then Purdom and Williams proved that

: $\lim_ \frac = \sqrt \lambda.$

Formulae

There are several expressions for $\lambda$. These include:

:$\lambda = \int_0^1 e^ \, dt$

where $\mathrm(t)$ is the logarithmic integral,

:$\lambda = \int_0^\infty e^ \, dt$

where $E_1(t)$ is the exponential integral, and

:$\lambda = \int_0^\infty \frac \, dt$

and

:$\lambda = \int_0^\infty \frac \, dt$

where $\rho(t)$ is the Dickman function.

See also

* Random permutation
* Random permutation statistics

External links

*
*
*

References

{{DEFAULTSORT:Golomb-Dickman constant
Mathematical constants
Permutations