質數公式

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

多項式形式的質數公式

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

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

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

${\displaystyle f(n)=n^{2}+n+41}$

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

狄利克雷定理證明了，對於互質的a和b， 線性函數 ${\displaystyle L(n)=an+b}$ 能產生無窮多個質數（儘管不是對於所有的自然數 ${\displaystyle n}$）。至於是否存在次數大於等於2的多項式，滿足對無窮多個整數，都能取到質數值，目前還沒有結論。

此外，格林-陶定理證明了另一結論：對於每個正整數 ${\displaystyle k}$，都存在著整數對 ${\displaystyle a}$, ${\displaystyle b}$，使得對於每個0與 ${\displaystyle k-1}$ 之間的 ${\displaystyle n}$，${\displaystyle L(n)=an+b}$ 都是質數。然而，對於比較大的 ${\displaystyle k}$，找出 ${\displaystyle a}$ 和 ${\displaystyle b}$ 是很困難的。目前最好的結果是對於 ${\displaystyle k=26}$^[1]，

P(n) = 5283234035979900n + 43142746595714191（ A204189 ）

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

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

${\displaystyle 0=wz+h+j-q}$

${\displaystyle 0=(gk+2g+k+1)(h+j)+h-z}$

${\displaystyle 0=16(k+1)^{3}(k+2)(n+1)^{2}+1-f^{2}}$

${\displaystyle 0=2n+p+q+z-e}$

${\displaystyle 0=e^{3}(e+2)(a+1)^{2}+1-o^{2}}$

${\displaystyle 0=(a^{2}-1)y^{2}+1-x^{2}}$

${\displaystyle 0=16r^{2}y^{4}(a^{2}-1)+1-u^{2}}$

${\displaystyle 0=n+l+v-y}$

${\displaystyle 0=(a^{2}-1)l^{2}+1-m^{2}}$

${\displaystyle 0=ai+k+1-l-i}$

${\displaystyle 0=((a+u^{2}(u^{2}-a))^{2}-1)(n+4dy)^{2}+1-(x+cu)^{2}}$

${\displaystyle 0=p+l(a-n-1)+b(2an+2a-n^{2}-2n-2)-m}$

${\displaystyle 0=q+y(a-p-1)+s(2ap+2a-p^{2}-2p-2)-x}$

${\displaystyle 0=z+pl(a-p)+t(2ap-p^{2}-1)-pm.}$

對於這個方程組的所有正整數解：${\displaystyle (a,b,\cdots ,z)}$，${\displaystyle k+2}$ 都是質數。可以把這個公式改寫成多項式的形式：將14個等式記作 ${\displaystyle p_{1},p_{2},\cdots ,p_{14}}$，那麼可以說，多項式${\displaystyle (k+2)(1-p_{1}^{2}-p_{2}^{2}-\cdots -p_{14}^{2})}$ 的輸入值${\displaystyle (a,b,\cdots ,z)}$是正整數時，其值域的正值部分就是所有質數。

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

帶高斯符號的質數公式

利用高斯符號${\displaystyle [x]}$，可以建立一些第 ${\displaystyle n}$ 個質數的表達式：

Mills公式

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

${\displaystyle [A^{3^{n}}\;]}$

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

威爾遜定理的利用

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

我們定義

${\displaystyle \pi (m)=\sum _{j=2}^{m}{\frac {\sin ^{2}({\pi \over j}(j-1)!^{2})}{\sin ^{2}({\pi \over j})}}}$

或者

${\displaystyle \pi (m)=\sum _{j=2}^{m}\left[{(j-1)!+1 \over j}-\left[{(j-1)! \over j}\right]\right].}$

這兩種定義是等價的。${\displaystyle \pi (m)}$就是小於 ${\displaystyle m}$ 的質數個數。於是，我們可以定義第 ${\displaystyle n}$ 個質數如下：

${\displaystyle p_{n}=1+\sum _{m=1}^{2^{n}}\left\lbrack \left\lbrack {n \over 1+\pi (m)}\right\rbrack ^{1 \over n}\right\rbrack .}$

另一個用高斯函數的例子

這個例子沒有用到階乘和威爾遜定理，但也大量應用了高斯函數（S. M. Ruiz 2000）。首先定義：

${\displaystyle \pi (k)=k-1+\sum _{j=2}^{k}\left\lbrack {2 \over j}\left(1+\sum _{s=1}^{\left\lbrack {\sqrt {j}}\right\rbrack }\left(\left\lbrack {j-1 \over s}\right\rbrack -\left\lbrack {j \over s}\right\rbrack \right)\right)\right\rbrack }$

然後就有第 ${\displaystyle n}$ 個質數的表達式：

${\displaystyle p_{n}=1+\sum _{k=1}^{2(\lbrack n\ln(n)\rbrack +1)}\left(1-\left\lbrack {\pi (k) \over n}\right\rbrack \right).}$

遞迴關係

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

${\displaystyle a_{n}=a_{n-1}+\operatorname {gcd} (n,a_{n-1}),\quad a_{1}=7,}$

其中 ${\displaystyle \gcd(x,y)}$ 表示 ${\displaystyle x}$ 和 ${\displaystyle y}$ 的最大公因數。這個數列的開始幾項 ${\displaystyle a_{n+1}-a_{n}}$ 是1, 1, 1, 5, 3, 1, 1, 1, 1, 11, 3, 1, 1 （OEIS數列A132199）。Rowlands (2008) harvtxt模板錯誤: 無指向目標: CITEREFRowlands2008 (幫助)證明了這個數列只含有一和質數。

其他公式

威爾遜定理衍生公式

${\displaystyle f(n)=2+(2n!\;{\pmod {n+1}})}$

其中，質數2出現無限多次，其餘的質數恰好出現一次。實際上，當 ${\displaystyle n+1}$ 是質數 ${\displaystyle p}$ 的時候，由威爾遜定理，${\displaystyle 2n!\;{\pmod {n+1}}}$等於p-2，於是${\displaystyle f(n)=p}$，當n+1是合數的時候，${\displaystyle 2n!{\pmod {n+1}}}$等於0，於是得到2。