素數公式

在數論中，質數公式是輸出質數的公式。計算素數的公式確實存在，但相比簡單的素數查找演算法，這類公式的計算速度就顯得非常慢。已知有若干限制條件，這些限制說明了這樣的「公式」可以是什麼，以及不能是什麼。

## 多項式形式的素數公式

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

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

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

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

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

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

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

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

## 丟番圖方程形式的素數公式

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

$$0 = wz + h + j - q$$

$$0 = (gk + 2g + k + 1)(h + j) + h - z$$

$$0 = 16(k + 1)^3(k + 2)(n + 1)^2 + 1 - f^2$$

$$0 = 2n + p + q + z - e$$

$$0 = e^3(e + 2)(a + 1)^2 + 1 - o^2$$

$$0 = (a^2 - 1)y^2 + 1 - x^2$$

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

$$0 = n + l + v - y$$

$$0 = (a^2 - 1)l^2 + 1 - m^2$$

$$0 = ai + k + 1 - l - i$$

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

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

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

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

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

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

## 帶高斯符號的素數公式

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

### Mills公式

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

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

中的每個數都是素數。最小的 $A$ 稱為米爾斯常數，如果黎曼猜想成立，它的值大約為：$A \approx 1.30637788386308069046\ldots$（A051021）。

這個素數公式並沒有什麼實際價值，因為人們對 $A$ 的性質所知甚少，甚至不知道 $A$ 是否為有理數。而且，除了用素數值逼近外，沒有其他計算 $A$ 的方法。

### 威爾遜定理的利用

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

我們定義

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

或者

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

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

$$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）。首先定義：

$$\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$$

然後就有第 $n$ 個素數的表達式：

$$p_n = 1 + \sum_{k=1}^{2(\lbrack n \ln(n)\rbrack+1)} \left(1 - \left\lbrack{\pi(k) \over n} \right\rbrack\right).$$

## 遞推關係

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

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

其中 $\gcd(x, y)$ 表示 $x$ 和 $y$ 的最大公因數。這個數列的開始幾項 $a_{n+1} - a_n$ 是1, 1, 1, 5, 3, 1, 1, 1, 1, 11, 3, 1, 1。證明了這個數列只含有一和素數。

## 其他公式

### 威爾遜定理衍生公式

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

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