Golomb-Dickman Constant
المؤلف:
Dickman, K
المصدر:
"On the Frequency of Numbers Containing Prime Factors of a Certain Relative Magnitude." Arkiv för Mat., Astron. och Fys
الجزء والصفحة:
...
18-2-2020
1872
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
(Shepp and Lloyd 1966, Wilf 1990), where 
is a harmonic number and 
is a generalized harmonic number.
In addition,
 |
(7)
|
(Shepp and Lloyd 1966, Wilf 1990). Goncharov (1942) showed that
 |
(8)
|
which is a Poisson distribution, and
![lim_(n->infty)P[(sum_(j=1)^inftyalpha_j-lnn)(lnn)^(-1/2)<=x]=Phi(x),](http://mathworld.wolfram.com/images/equations/Golomb-DickmanConstant/NumberedEquation3.gif) |
(9)
|
which is a normal distribution, 
is the Euler-Mascheroni constant, and 
is the normal distribution function.
Let
![M(alpha)=max_(j)<span style=]() {j:alpha_j>0}, " src="http://mathworld.wolfram.com/images/equations/Golomb-DickmanConstant/NumberedEquation4.gif" style="height:29px; width:140px" /> |
(10)
|
i.e., the length of the longest cycle in 
. 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 
and 
such that
![lim_(n->infty)n^b[<M(alpha)>-lambdan-1/2lambda]=c,](http://mathworld.wolfram.com/images/equations/Golomb-DickmanConstant/NumberedEquation5.gif) |
(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
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
![F(x)=lim_(n->infty)P(x,n)=<span style=]() {1 if x>=1; int_0^xF(t/(1-t))(dt)/t if 0<=x<1, " src="http://mathworld.wolfram.com/images/equations/Golomb-DickmanConstant/NumberedEquation10.gif" style="height:62px; width:315px" /> |
(21)
|
where 
is now known as the Dickman function. Dickman then found the average value of 
such that 
, obtaining
which is identical to 
.
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.
الاكثر قراءة في نظرية الاعداد
اخر الاخبار
اخبار العتبة العباسية المقدسة
