素数公式

质数公式，又称素数公式，在数学领域中，表示一种能够仅产生素数的公式。即是说，这个公式能够一个不漏地产生所有的素数，并且对每个输入的值，此公式产生的结果都是素数。由于素数的个数是可数的，因此一般假设输入的值是自然数集（或整数集及其它可数集）。迄今为止，人们尚未找到易于计算且符合上述条件的素数公式，但对于素数公式应该具备的性质已经有了大量的研究。

多项式形式的素数公式

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