素数公式

在数论中，质数公式是输出质数的公式。计算素数的公式确实存在，但相比简单的素数查找算法，这类公式的计算速度就显得非常慢。已知有若干限制条件，这些限制说明了这样的“公式”可以是什么，以及不能是什么。

## 多项式形式的素数公式

可以证明，一个整系数多项式 $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。