TOPICS

Golomb-Dickman Constant

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

 (1) (2) (3) (4) (5) (6)

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

 (7)

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

 (8)

which is a Poisson distribution, and

 (9)

which is a normal distribution, is the Euler-Mascheroni constant, and is the normal distribution function.

Let

 (10)

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

 (11) (12)

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

Knuth (1997) asked for the constants and such that

 (13)

and Gourdon (1996) showed that

 (14)

where

 (15)

can be expressed in terms of the function defined by for and

 (16)

for , by

 (17)

Shepp and Lloyd (1966) derived

 (18) (19) (20)

where is the logarithmic integral.

Surprisingly, there is a connection between and prime factorization (Knuth and Pardo 1976, Knuth 1997, pp. 367-368, 395, and 611). Dickman (1930) investigated the probability that the greatest prime factor of a random integer between 1 and satisfies for . He found that

 (21)

where is now known as the Dickman function. Dickman then found the average value of such that , obtaining

 (22) (23) (24) (25) (26)

which is identical to .

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

Explore with Wolfram|Alpha

More things to try:

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