主題
Search

Golomb-Dickman 常數

DOWNLOAD Mathematica Notebook下載 Wolfram 筆記本

設 Pi 為 n 個元素的排列，並設 alpha_i 為此排列中長度為 i 的排列環的數量。隨機選取 Pi，結果表明

<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 和 Lloyd 1966, Wilf 1990)，其中 H_n 是調和數，而 H_(n,r) 是廣義調和數。

此外，

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

(Shepp 和 Lloyd 1966, Wilf 1990)。Goncharov (1942) 表明

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

這是一個泊松分佈，且

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

這是一個正態分佈，gamma 是 尤拉-馬歇羅尼常數，而 Phi(x) 是正態分佈函式。

設

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

即，Pi 中最長環的長度。Golomb (1964) 計算了定義為以下常數的近似值（誤差較大）

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

(OEIS A084945) 並且被稱為 Golomb 常數或 Golomb-Dickman 常數。

Knuth (1997) 詢問了常數 b 和 c，使得

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

而 Gourdon (1996) 表明

<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)

其中

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

lambda 可以用函式 f(x) 表示，該函式定義為 f(x)=1，當 1<=x<=2 時，且

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

對於 x>2，透過

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

Shepp 和 Lloyd (1966) 推匯出

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)

其中 li(x) 是對數積分。

令人驚訝的是，lambda 和素因數分解之間存在聯絡 (Knuth 和 Pardo 1976, Knuth 1997, pp. 367-368, 395, 和 611)。Dickman (1930) 研究了機率 P(x,n)，即介於 1 和 n 之間的隨機整數的最大素因數 p 滿足 p<n^x，對於 x in (0,1)。他發現

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)

其中 F(x) 現在被稱為 Dickman 函式。Dickman 隨後找到了 x 的平均值，使得 p=n^x，得到

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)

這與 lambda 相同。

另請參閱

常數素數, Dickman 函式, Golomb-Dickman 常數連分數, Golomb-Dickman 常數數字, 最大素因數, 整數序列素數

使用 探索

參考文獻

Dickman, K. "關於包含具有特定相對大小的素因子的數的頻率。" Arkiv för Mat., Astron. och Fys. 22A, 1-14, 1930.Finch, S. R. "Golomb-Dickman 常數。" Mathematical Constants 第 §5.4 節. Cambridge, England: Cambridge University Press, pp. 284-292, 2003.Golomb, S. W. "隨機排列。" 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. "關於組合分析領域。" 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. "簡單因式分解演算法的分析。" Theor. Comput. Sci. 3, 321-348, 1976.Mitchell, W. C. "Golomb 常數的評估。" Math. Comput. 22, 411-415, 1968.Purdom, P. W. and Williams, J. H. "隨機函式中的環長。" Trans. Amer. Math. Soc. 133, 547-551, 1968.Shepp, L. A. and Lloyd, S. P. "隨機排列中的有序環長。" Trans. Amer. Math. Soc. 121, 350-557, 1966.Sloane, N. J. A. Sequences A084945, A174974, and A174975 in "整數序列線上百科全書."Wilf, H. S. Generatingfunctionology, 2nd ed. New York: Academic Press, 1994.

在 中引用

Golomb-Dickman 常數

請引用為

Weisstein, Eric W. "Golomb-Dickman 常數。" 來自 —— 資源。 https://mathworld.tw/Golomb-DickmanConstant.html

主題分類