質數公式

質數公式,又稱素數公式,在數學領域中,表示一種能夠僅產生質數的公式。即是說,這個公式能夠一個不漏地產生所有的質數,並且對每個輸入的值,此公式產生的結果都是質數。由於質數的個數是可數的,因此一般假設輸入的值是自然數集(或整數集及其它可數集)。迄今為止,人們尚未找到易於計算且符合上述條件的質數公式,但對於質數公式應該具備的性質已經有了大量的研究。

多項式形式的質數公式

可以證明,一個整系數多項式P(n),如果不是常數函數的話,不會是一個質數公式。證明很簡單:假設這樣的一個多項式P(n)存在。那麼P(1)將是一個質數p。接下來考慮 的值。由於 ,對於任意整數k,我們有 ,從而 p的倍數,但已然假設 是質數公式,所以 必須是質數,於是它就只能等於 。也就是說,對於任意的k 都是多項式P(n) - p的一個。但根據代數基本定理,一個非零的整系數多項式不可能有無窮多個根。故此,P(n)只能是常數函數。

應用代數數理論,可以證明更強的結果:不存在能夠對幾乎所有自然數輸入,都能產生質數的非常數的多項式P(n)。

歐拉在1772年發現,對於小於40的所有自然數,多項式

 

的值都是質數。對於前幾個自然數n = 0, 1, 2, 3...,多項式的值是41, 43, 47, 53, 61, 71...。當n等於40時,多項式的值是1681=41×41,是一個合數。實際上,當n能被41整除的時候,P(n)也能被41整除,因而是合數。這個公式和所謂的質數螺旋有關,也和黑格納數 有關。若 時,其對應的多項式也有類似的性質,而 也是黑格納數。

狄利克雷定理證明了,對於互質ab線性函數 能產生無窮多個質數(儘管不是對於所有的自然數n)。至於是否存在次數大於等於2的多項式,滿足對無窮多個整數,都能取到質數值,目前還沒有結論。

此外,格林-陶定理證明了另一結論:對於每個正整數k,都存在着整數對a, b,使得對於每個0與k−1之間的n 都是質數。然而,對於比較大的k,找出ab是很困難的。目前最好的結果是對於k = 26[1]

P(n) = 5283234035979900n + 43142746595714191( A204189

丟番圖方程形式的質數公式

一個很著名的質數公式是以下的有26個未知數的由14個方程組成的丟番圖方程組Jones et al.(1976):

 
 
 
 
 
 
 
 
 
 
 
 
 
 

對於這個方程組的所有正整數解:(a,b,...,z),k + 2都是質數。可以把這個公式改寫成多項式的形式:將14個等式記作p1,p2,……,p14,那麼可以說,多項式 的輸入值(a,b,...,z)是正整數時,其值域的正值部分就是所有質數。

根據尤里·馬季亞謝維奇的一個定理,如果一個集合能夠被定義成一個丟番圖方程的解集,那麼就可以被定義為一個只有9個未知數的丟番圖方程的解集。於是,質數集合可以被定義為一個只含10個變元的多項式的正值解集。然而,這個多項式的次數極大(在1045數量級),另一方面,也存在次數不超過4的多項式,未知數個數是58個。

帶高斯符號的質數公式

利用高斯符號 ,可以建立一些第n個質數的表達式:

Mills公式

第一個帶高斯函數的質數公式由W. H. Mills在1947年構造。他證明了存在實數A使得數列

 

中的每個數都是質數。最小的A稱為米爾斯常數,如果黎曼猜想成立,它的值大約為:  A051021)。 這個質數公式並沒有什麼實際價值,因為人們對A的性質所知甚少,甚至不知道A是否為有理數。而且,除了用質數值逼近外,沒有其他計算A的方法。

威爾遜定理的利用

使用威爾遜定理,可以建立一些其他的質數公式。以下的公式也沒有什麼實際價值,大多數的質數測試都比它遠為有效。

我們定義

 

或者

 

這兩種定義是等價的。π(m)就是小於m的質數個數。於是,我們可以定義第n個質數如下:

 

另一個用高斯函數的例子

這個例子沒有用到階乘威爾遜定理,但也大量應用了高斯函數(S. M. Ruiz 2000)。首先定義:

 

然後就有第n個質數的表達式:

 

遞歸關係

另外一個質數公式由以下遞歸關係組成的數列,其前後項的差來定義:

 

其中gcd(x, y)表示xy最大公因數。這個數列的開始幾項an+1 - an是1, 1, 1, 5, 3, 1, 1, 1, 1, 11, 3, 1, 1 (OEIS數列A132199)。Rowlands (2008)證明了這個數列只含有一和質數。

其他公式

威爾遜定理衍生公式

 

其中,質數2出現無限多次,其餘的質數恰好出現一次。實際上,當n+1是質數p的時候,由威爾遜定理 等於p-2,於是 ,當n+1是合數的時候, 等於0,於是得到2。

參考資料

  1. ^ PrimeGrid’s AP26 Search (PDF). [2015-03-07]. (原始內容存檔 (PDF)於2020-09-21). 

參見