Golomb-Dickman Constant

Let Pi be a permutation of n elements, and let alpha_i be the number of permutation cycles of length i in this permutation. Picking Pi at random, it turns out that


(Shepp and Lloyd 1966, Wilf 1990), where H_n is a harmonic number and H_(n,r) is a generalized harmonic number.

In addition,


(Shepp and Lloyd 1966, Wilf 1990). Goncharov (1942) showed that


which is a Poisson distribution, and


which is a normal distribution, gamma is the Euler-Mascheroni constant, and Phi(x) is the normal distribution function.



i.e., the length of the longest cycle in Pi. Golomb (1964) computed an approximation (with a sizable error) to the constant defined as


(OEIS A084945) and which is known as the Golomb constant or Golomb-Dickman constant.

Knuth (1997) asked for the constants b and c such that


and Gourdon (1996) showed that




lambda can be expressed in terms of the function f(x) defined by f(x)=1 for 1<=x<=2 and


for x>2, by


Shepp and Lloyd (1966) derived


where li(x) is the logarithmic integral.

Surprisingly, there is a connection between lambda and prime factorization (Knuth and Pardo 1976, Knuth 1997, pp. 367-368, 395, and 611). Dickman (1930) investigated the probability P(x,n) that the greatest 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)=lim_(n->infty)P(x,n)={1   if x>=1; int_0^xF(t/(1-t))(dt)/t   if 0<=x<1,

where F(x) is now known as the Dickman function. Dickman then found the average value of x such that p=n^x, obtaining


which is identical to lambda.

See also

Constant Primes, Dickman Function, Golomb-Dickman Constant Continued Fraction, Golomb-Dickman Constant Digits, Greatest Prime Factor, Integer Sequence Primes

Explore with Wolfram|Alpha


Dickman, K. "On the Frequency of Numbers Containing Prime Factors of a Certain Relative Magnitude." Arkiv för Mat., Astron. och Fys. 22A, 1-14, 1930.Finch, S. R. "Golomb-Dickman Constant." §5.4 in Mathematical Constants. Cambridge, England: Cambridge University Press, pp. 284-292, 2003.Golomb, S. W. "Random Permutations." Bull. Amer. Math. Soc. 70, 747, 1964.Goncharov, W. "Sur la distribution des cycles dans les permutations." C. R. (Dokl.) Acad. Sci. URSS 35, 267-269, 1942.Goncharov, W. "On the Field of Combinatory Analysis." Izv. Akad. Nauk SSSR 8, 3-48, 1944. English translation in Amer. Math. Soc. Transl. 19, 1-46, 1962.Gourdon, X. Combinatoire, Algorithmique et Géometrie des Polynômes. Ph. D. thesis. École Polytechnique, 1996.Knuth, D. E. The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 3rd ed. Reading, MA: Addison-Wesley, 1997.Knuth, D. E. The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 3rd ed. Reading, MA: Addison-Wesley, 1998.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.Sloane, N. J. A. Sequences A084945, A174974, and A174975 in "The On-Line Encyclopedia of Integer Sequences."Wilf, H. S. Generatingfunctionology, 2nd ed. New York: Academic Press, 1994.

Referenced on Wolfram|Alpha

Golomb-Dickman Constant

Cite this as:

Weisstein, Eric W. "Golomb-Dickman Constant." From MathWorld--A Wolfram Web Resource.

Subject classifications