TOPICS
Search

Golomb-Dickman Constant

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

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

<sum_(j=1)^(infty)alpha_j>=sum_(i=1)^(n)1/i
(1)
=H_n
(2)
=lnn+gamma+O(1/n)
(3)
var(sum_(j=1)^(infty)alpha_j)=sum_(i=1)^(n)(i-1)/(i^2)
(4)
=H_n-H_(n,2)
(5)
=lnn-n+gamma-1/2-1/6pi^2+O(1/n)
(6)

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

In addition,

lim_(n->infty)P(alpha_1=0)=1/e
(7)

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

lim_(n->infty)P(alpha_j=k)=1/(k!)e^(-1/j)j^(-k),
(8)

which is a Poisson distribution, and

lim_(n->infty)P[(sum_(j=1)^inftyalpha_j-lnn)(lnn)^(-1/2)<=x]=Phi(x),
(9)

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

Let

M(alpha)=max_(j){j:alpha_j>0},
(10)

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

lambda=lim_(n->infty)(<M(alpha)>)/n
(11)
=0.6243299885...
(12)

(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

lim_(n->infty)n^b[<M(alpha)>-lambdan-1/2lambda]=c,
(13)

and Gourdon (1996) showed that

<M(alpha)>=lambda(n+1/2)-(e^gamma)/(24n)+(1/(48)e^gamma-1/8(-1)^n)/(n^2)+((17)/(3840)e^gamma+1/8(-1)^n+1/6j^(1+2n)+1/6j^(2+n))/(n^3),
(14)

where

j=e^(2pii/3).
(15)

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

(df)/(dx)=-(f(x-1))/(x-1)
(16)

for x>2, by

lambda=int_1^infty(f(x))/(x^2)dx.
(17)

Shepp and Lloyd (1966) derived

lambda=int_0^inftyexp(-x-int_x^infty(e^(-y))/ydy)dx
(18)
=int_0^1exp(int_0^x(dy)/(lny))dx
(19)
=int_0^1e^(li(x))dx,
(20)

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,
(21)

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

mu=lim_(n->infty)<x>
(22)
=lim_(n->infty)<(lnp)/(lnn)>
(23)
=int_0^1x(dF)/(dx)dx
(24)
=int_0^1F(t/(1-t))dt
(25)
=0.62432999,
(26)

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

References

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 Resource. https://mathworld.wolfram.com/Golomb-DickmanConstant.html

Subject classifications