主题
Search

素数公式

存在多种公式，用于生成第 n 个素数作为 n 的函数，或者仅取素数值。然而，所有这些公式都需要极其精确地了解一些未知的常数，或者实际上需要预先知道素数才能使用该公式 (Dudley 1969; Ribenboim 1996, p. 186)。还存在简单的素数生成多项式，它们在前（可能很大）个整数值中仅生成素数。

还有许多涉及素数和与素数积的美丽公式，可以用闭合形式完成。

考虑到仅生成素数的公式示例（尽管不一定是素数P的完整集合），存在一个常数theta=1.3063... (OEIS A051021) 称为 Mills' 常数，使得

f(n)=|_theta^(3^n)_|,
(1)

其中 |_x_| 是向下取整函数，对于所有 n>=1 都是素数 (Ribenboim 1996, p. 186)。 f(n) 的前几个值是 2, 11, 1361, 2521008887, ... (OEIS A051254)。尚不清楚 theta 是否是无理数。还存在一个常数omega approx 1.9287800 (OEIS A086238) 使得

g(n)=|_2omegan_|
(2)

(Wright 1951; Ribenboim 1996, p. 186) 对于每个 n>=1 都是素数。g(n) 的前几个值是 3, 13, 16381, ... (OEIS A016104)。在 f(n) 和 g(n) 两种情况下，当 n=4 时，数字增长得如此迅速，以至于需要极其精确的 theta 或 omega 值才能获得正确的值，并且 n>=5 的值实际上是不可计算的。

存在 n 个素数的显式公式，既可以是 n 的函数，也可以用素数 2, ..., p_(n-1) 表示 (Hardy and Wright 1979, pp. 5-6, 344-345, and 414; Guy 1994, pp. 36-41)，下面给出了一些。然而，应该再次强调的是，这些公式效率极低，并且在许多（如果不是全部）情况下，简单地执行高效的筛选将更快更有效地产生素数。

有时被称为 Willans 公式的素数生成公式可以构造如下。设

F(j)=|_cos^2[pi((j-1)!+1)/j]_|
(3)
={1 for j=1 or j prime; 0 otherwise
(4)

对于 j>1 整数，其中 |_x_| 再次是向下取整函数。这个公式是 威尔逊定理 的一个结果，并且隐藏了素数 j，即对于这些素数，F(j)=1，即 F(j) 的值是 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, ... (OEIS A080339)。然后

pi(x)=-1+sum_(k=1)^xF(k)
(5)

和

p_n=1+sum_(m=1)^(2^n)|_|_n/(sum_(j=1)^(m)F(j))_|^(1/n)_|
(6)
=1+sum_(m=1)^(2^n)|_|_n/(1+pi(m))_|^(1/n)_|,
(7)

其中 pi(m) 是素数计数函数 (Willans 1964; Havil 2003, pp. 168-169)。

Gandhi 给出了公式，其中 p_(n+1) 是唯一的整数，使得

1<2^(p_(n+1))(sum_(d|p_n#)(mu(d))/(2^d-1)-1/2)<2,
(8)

其中 p_n# 是素数阶乘函数 (Gandhi 1971, Eynden 1972, Golomb 1974)，mu(n) 是莫比乌斯函数。同样也成立

p_(n+1)=1+p_n+F(p_n+1)+F(p_n+1)F(p_n+2)+product_(j=1)^pF(p_n+j)
(9)

(Ribenboim 1996, pp. 180-182)。请注意，求和中获得第 n 个素数的项数为 2^n，因此这些公式最终在素数研究中并不实用。

Hardy 和 Wright (1979, p. 414) 给出了公式

p_n=1+sum_(j=1)^(2^n)f(n,pi(j)),
(10)

对于 n>3，其中

f(x,y)={0 for x=y; 1/2[1+(x-y)/(|x-y|)] for x!=y
(11)

并且 素数计数函数 的“基本”公式由下式给出

pi(n)=-1+sum_(j=3)^n[(j-2)!-j|_((j-2)!)/j_|]
(12)

（修正了符号错误），其中 |_x_| 是向下取整函数。

第 n 个素数 p_n 的双重求和为

p_n=1+sum_(k=1)^(2(|_nlnn_|+1))[1-|_(sum_(j=2)^(k)1+|_s(j)_|)/n_|],
(13)

其中

s(j)=-(sum_(s=1)^(j)(|_j/s_|-|_(j-1)/s_|)-2)/j
(14)

(Ruiz 2000)。

PrimeFormulaCipolla

p_n 的渐近公式由下式给出

p_n∼n(lnn+lnlnn-1+(lnlnn-2)/(lnn)-(ln^2(lnn)-6lnlnn+11)/(2ln^2n)+...)
(15)

(Cipolla 1902)。这个渐近展开是对数积分 Li(x) 通过级数反演获得的逆，其中 Li(x) 的反演给出 p_n，因为素数定理表明 Li(x)∼pi(x)，其中 pi(x) 是素数计数函数，而 pi(x) 的反函数是 p_n，因为 pi(p_n)=n。然而，如上图所示，该公式振荡很大，其中 p_n-p^^_n 是实际的第 n 个素数与 Cipolla 公式给出的素数之间的差值。有趣的是，截断为 n(lnn+lnlnn-1) 给出了 Rosser 定理的改进形式，这是一个关于 p_n 的严格不等式。Salvy (1994) 处理了更一般的情况。

PrimeFormulaBredihin

B. M. Bredihin 证明了

f(x,y)=x^2+y^2+1
(16)

对于无限多的整数对 (x,y) (Honsberger 1976, p. 30) 取素数值。例如，f(1,1)=3、f(1,3)=11、f(1,9)=83 等等。这种形式的素数是 3, 11, 19, 41, 53, 59, 73, 83, 101, 107, 131, 137, 149, 163, ... (OEIS A079544; Mitrinović 和 Sándor 1995, p. 11)。使 f(x,y) 为素数的 x 和 y 的值在上面绘制，显示了一些有趣的模式。

通常，人为构造总是生成素数的公式并不困难。例如，考虑公式

f(x,y)=1/2(y-1)[|B^2(x,y)-1|-(B^2(x,y)-1)]+2,
(17)

其中

B(x,y)=x(y+1)-(y!+1),
(18)

其中 y! 是阶乘，而 x 和 y 是正整数 (Honsberger 1976, p. 33)。除非 x=[(p-1)!+1]/p 且 y=p-1，否则这将始终具有 B(x,y)^2>1，因此产生值 2，在这种情况下，它简化为

f(((p-1)!+1)/p,p-1)=p
(19)

因此，该公式在 威尔逊商 x=[(p-1)!+1]/p 为整数，即 1, 1, 5, 103, 329891, 36846277, 1230752346353, ... (OEIS A007619) 的值处，精确地生成每个奇素数一次 (Honsberger 1976, p. 33)。

FRACTRAN 游戏（Guy 1983, Conway 和 Guy 1996, p. 147）提供了一种基于 14 个分数生成素数的意外方法，但它实际上只是筛选法的隐藏版本。

参见

FRACTRAN, Mills' 常数, 素数计数函数, 素数, 素数积, 素数和, Rosser 定理, 筛选法, Willans 公式

相关 Wolfram 站点

http://functions.wolfram.com/NumberTheoryFunctions/Prime/

使用 Wolfram|Alpha 探索

参考文献

Cipolla, M. ""La determinazione assintotica dell'n^(imo) numero primo." Napoli Rend. 3, 132-166, 1902.Conway, J. H. and Guy, R. K. The Book of Numbers. New York: Springer-Verlag, pp. 130 and 147, 1996.Dudley, U. "History of Formula for Primes." Amer. Math. Monthly 76, 23-28, 1969.Dusart, P. "The k^(th) Prime is Greater than k(lnk+lnlnk-1) for k>=2." Math. Comput. 68, 411-415, 1999.Eynden, C. V. "A Proof of Gandhi's Formula for the nth Prime." Amer. Math. Monthly 79, 625, 1972.Finch, S. R. "Hardy-Littlewood Constants." §2.1 in Mathematical Constants. Cambridge, England: Cambridge University Press, pp. 84-94, 2003.Gandhi, J. M. "Formulae for the Nth Prime." Proc. Washington State University Conferences on Number Theory. pp. 96-107, 1971.Gardner, M. "Patterns and Primes." Ch. 9 in The Sixth Book of Mathematical Games from Scientific American. Chicago, IL: University of Chicago Press, pp. 79-90, 1984.Golomb, S. W. "A Direct Interpretation of Gandhi's Formula." Amer. Math. Monthly 81, 752-754, 1974.Guy, R. K. "Conway's Prime Producing Machine." Math. Mag. 56, 26-33, 1983.Guy, R. K. "Prime Numbers," "Formulas for Primes," and "Products Taken over Primes." Ch. A, §A17, and §B48 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 3-43, 36-41, and 102-103, 1994.Hardy, G. H. and Wright, E. M. "Prime Numbers" and "The Sequence of Primes." §1.2 and 1.4 in An Introduction to the Theory of Numbers, 5th ed. Oxford, England: Clarendon Press, pp. 1-4, 5-6, 344-345, and 414, 1979.Havil, J. Gamma: Exploring Euler's Constant. Princeton, NJ: Princeton University Press, 2003.Honsberger, R. Mathematical Gems II. Washington, DC: Math. Assoc. Amer., 1976.Mills, W. H. "A Prime-Representing Function." Bull. Amer. Math. Soc. 53, 604, 1947.Mitrinović, D. S. and Sándor, J. Handbook of Number Theory. Dordrecht, Netherlands: Kluwer, 1995.Ribenboim, P. The New Book of Prime Number Records. New York: Springer-Verlag, 1996.Ruiz, S. M. "The General Term of the Prime Number Sequence and the Smarandache Prime Function." Smarandache Notions J. 11, 59-61, 2000.Salvy, B. "Fast Computation of Some Asymptotic Functional Inverses." J. Symb. Comput. 17, 227-236, 1994.Sloane, N. J. A. Sequences A007619/M4023, A016104, A051021, A051254, A079544, A080339, and A086238 in "The On-Line Encyclopedia of Integer Sequences."Willans, C. P. "A Formula for the nth Prime Number." Math. Gaz. 48, 413-415, 1964.Wright, E. M. "A Prime-Representing Function." Amer. Math. Monthly 58, 616-618, 1951.

在 Wolfram|Alpha 上被引用

素数公式

请引用为

Eric Weisstein “素数公式。” 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/PrimeFormulas.html

学科分类