info prev up next book cdrom email home

Golomb-Dickman Constant

N.B. A detailed on-line essay by S. Finch was the starting point for this entry.

Let $\Pi$ be a Permutation of $n$ elements, and let $\alpha_i$ be the number of Cycles of length $i$ in this Permutation. Picking $\Pi$ at Random gives

\left\langle{\,\sum_{j=1}^\infty \alpha_j}\right\rangle{} = ...
... {1\over i} = \ln n+\gamma+{\mathcal O}\left({1\over n}\right)
\end{displaymath} (1)

\mathop{\rm var}\nolimits \left({\,\sum_{j=1}^\infty \alpha_...
...\textstyle{1\over 6}}\pi^2+{\mathcal O}\left({1\over n}\right)
\end{displaymath} (2)

\lim_{n\to\infty} P(\alpha_1=0)={1\over e}
\end{displaymath} (3)

(Shepp and Lloyd 1966, Wilf 1990). Goncharov (1942) showed that
\lim_{n\to\infty} P(\alpha_j=k)={1\over k!}e^{-1/j}j^{-k},
\end{displaymath} (4)

which is a Poisson Distribution, and
\lim_{n\to\infty} P\left[{\left({\,\sum_{j=1}^\infty \alpha_j-\ln n}\right)(\ln n)^{-1/2}\leq x}\right]=\Phi(x),
\end{displaymath} (5)

which is a Normal Distribution, $\gamma$ is the Euler-Mascheroni Constant, and $\Phi$ is the Normal Distribution Function. Let
$\displaystyle M(\alpha)$ $\textstyle \equiv$ $\displaystyle \max_{1\leq j<\infty} \alpha_j$ (6)
$\displaystyle m(\alpha)$ $\textstyle \equiv$ $\displaystyle \min_{1\leq j<\infty} \alpha_j.$ (7)

Golomb (1959) derived
\lambda\equiv\lim_{n\to\infty} {\left\langle{M(\alpha)}\right\rangle{}\over n}=0.6243299885\ldots,
\end{displaymath} (8)

which is known as the Golomb Constant or Golomb-Dickman constant. Knuth (1981) asked for the constants $b$ and $c$ such that
\lim_{n\to\infty} n^b[\left\langle{M(\alpha)}\right\rangle{}-\lambda n-{\textstyle{1\over 2}}\lambda]=c,
\end{displaymath} (9)

and Gourdon (1996) showed that

...e{1\over 6}} j^{1+2n}+{\textstyle{1\over 6}}j^{2+n}\over n^3},
\end{displaymath} (10)

j\equiv e^{2\pi i/3}.
\end{displaymath} (11)

$\lambda$ can be expressed in terms of the function $f(x)$ defined by $f(x)=1$ for $1\leq x\leq 2$ and
{df\over dx}=-{f(x-1)\over x-1}
\end{displaymath} (12)

for $x>2$, by
\lambda=\int_1^\infty {f(x)\over x^2}\,dx.
\end{displaymath} (13)

Shepp and Lloyd (1966) derived
$\displaystyle \lambda$ $\textstyle =$ $\displaystyle \int_0^\infty \mathop{\rm exp}\nolimits \left({-x-\int_x^\infty {e^{-y}\over y}\, dy}\right)$  
  $\textstyle =$ $\displaystyle \int_0^1 \mathop{\rm exp}\nolimits \left({\,\int_0^x {dy\over \ln y}}\right)\,dx.$ (14)

Mitchell (1968) computed $\lambda$ to 53 decimal places.

Surprisingly enough, there is a connection between $\lambda$ and Prime Factorization (Knuth and Pardo 1976, Knuth 1981, pp. 367-368, 395, and 611). Dickman (1930) investigated the probability $P(x,n)$ that the largest Prime Factor $p$ of a random Integer between 1 and $n$ satisfies $p<n^x$ for $x\in(0,1)$. He found that

F(x)\equiv \lim_{n\to\infty} P(x,n) =\cases{
1 & if $x\geq ...
...^x F\left({t\over 1-t}\right){dt\over t} & if $0\leq x<1$.\cr}
\end{displaymath} (15)

Dickman then found the average value of $x$ such that $p=n^x$, obtaining
$\displaystyle \mu$ $\textstyle \equiv$ $\displaystyle \lim_{n\to\infty} \left\langle{x}\right\rangle{}=\lim_{n\to\infty} \left\langle{\ln p\over\ln n}\right\rangle{}=\int_0^1 x{dF\over dx}\,dx$  
  $\textstyle =$ $\displaystyle \int_0^1 F\left({1\over 1-t}\right)\,dt=0.62432999,$ (16)

which is $\lambda$.


Finch, S. ``Favorite Mathematical Constants.''

Gourdon, X. 1996.

Knuth, D. E. The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 2nd ed. Reading, MA: Addison-Wesley, 1973.

Knuth, D. E. The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 2nd ed. Reading, MA: Addison-Wesley, 1981.

Knuth, D. E. and Pardo, L. T. ``Analysis of a Simple Factorization Algorithm.'' Theor. Comput. Sci. 3, 321-348, 1976.

Mitchell, W. C. ``An Evaluation of Golomb's Constant.'' Math. Comput. 22, 411-415, 1968.

Purdom, P. W. and Williams, J. H. ``Cycle Length in a Random Function.'' Trans. Amer. Math. Soc. 133, 547-551, 1968.

Shepp, L. A. and Lloyd, S. P. ``Ordered Cycle Lengths in Random Permutation.'' Trans. Amer. Math. Soc. 121, 350-557, 1966.

Wilf, H. S. Generatingfunctionology, 2nd ed. New York: Academic Press, 1993.

info prev up next book cdrom email home

© 1996-9 Eric W. Weisstein