主題
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/

使用 探索

參考文獻

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.

在 上被引用

素數公式

請引用為

Eric Weisstein “素數公式。” 來自 Web 資源。 https://mathworld.tw/PrimeFormulas.html

學科分類