主题
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 常数数字, 最大素因数, 整数序列素数

使用 Wolfram|Alpha 探索

参考文献

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.

在 Wolfram|Alpha 中引用

Golomb-Dickman 常数

请引用为

Weisstein, Eric W. "Golomb-Dickman 常数。" 来自 MathWorld——Wolfram Web 资源。 https://mathworld.net.cn/Golomb-DickmanConstant.html

主题分类