质数公式,又称素数公式,在数学领域中,表示一种能够仅产生素数的公式。即是说,这个公式能够一个不漏地产生所有的素数,并且对每个输入的值,此公式产生的结果都是素数。由于素数的个数是可数的,因此一般假设输入的值是自然数集(或整数集及其它可数集)。迄今为止,人们尚未找到易于计算且符合上述条件的素数公式,但对于素数公式应该具备的性质已经有了大量的研究。
可以证明,一个整系数多项式P(n),如果不是常数函数的话,不会是一个素数公式。证明很简单:假设这样的一个多项式P(n)存在。那么P(1)将是一个素数p。接下来考虑
的值。由于
,对于任意整数k,我们有
,从而
是p的倍数,但已然假设
是素数公式,所以
必须是素数,于是它就只能等于
。也就是说,对于任意的k,
都是多项式P(n) - p的一个根。但根据代数基本定理,一个非零的整系数多项式不可能有无穷多个根。故此,P(n)只能是常数函数。
应用代数数理论,可以证明更强的结果:不存在能够对几乎所有自然数输入,都能产生素数的非常数的多项式P(n)。
欧拉在1772年发现,对于小于40的所有自然数,多项式
![{\displaystyle f(n)=n^{2}+n+41}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/51ed772ab811fded4669efa8bde0218a44567d03)
的值都是素数。对于前几个自然数n = 0, 1, 2, 3...,多项式的值是41, 43, 47, 53, 61, 71...。当n等于40时,多项式的值是1681=41×41,是一个合数。实际上,当n能被41整除的时候,P(n)也能被41整除,因而是合数。这个公式和所谓的素数螺旋有关,也和黑格纳数
有关。若
时,其对应的多项式也有类似的性质,而
也是黑格纳数。
狄利克雷定理证明了,对于互素的a和b, 线性函数
能产生无穷多个素数(尽管不是对于所有的自然数n)。至于是否存在次数大于等于2的多项式,满足对无穷多个整数,都能取到素数值,目前还没有结论。
此外,格林-陶定理证明了另一结论:对于每个正整数k,都存在着整数对a, b,使得对于每个0与k−1之间的n,
都是素数。然而,对于比较大的k,找出a和b是很困难的。目前最好的结果是对于k = 26[1],
- P(n) = 5283234035979900n + 43142746595714191(
A204189 )
一个很著名的素数公式是以下的有26个未知数的由14个方程组成的丢番图方程组Jones et al.(1976):
![{\displaystyle 0=wz+h+j-q}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/aff045947309e85a75a31ddadaa932f232aebc93)
![{\displaystyle 0=(gk+2g+k+1)(h+j)+h-z}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/17fae7143cf5fc20ff9f6ab5035b608672a0bd44)
![{\displaystyle 0=16(k+1)^{3}(k+2)(n+1)^{2}+1-f^{2}}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/5bc02dc5f4344c8b18ab213302040a06185295f0)
![{\displaystyle 0=2n+p+q+z-e}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/43a56e80995bda65dbb35bb95c94431d082cab9b)
![{\displaystyle 0=e^{3}(e+2)(a+1)^{2}+1-o^{2}}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/f95d23442705517ad0873937dc1b70fffaa82515)
![{\displaystyle 0=(a^{2}-1)y^{2}+1-x^{2}}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/1cf151c1be238dc1178e9d8ea5b9253fe6c5f078)
![{\displaystyle 0=16r^{2}y^{4}(a^{2}-1)+1-u^{2}}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/ce0c16f54f6e3d9a3e0a96db84592c0b94b0cefd)
![{\displaystyle 0=n+l+v-y}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/2e0ba0424df7e7e030b71652f78ce8b34994b122)
![{\displaystyle 0=(a^{2}-1)l^{2}+1-m^{2}}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/5df8079f46c6a7c8c86b5ec79b85184c07893551)
![{\displaystyle 0=ai+k+1-l-i}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/82c05a5d3441f85a3f288fc01c95e1d00a466ea0)
![{\displaystyle 0=((a+u^{2}(u^{2}-a))^{2}-1)(n+4dy)^{2}+1-(x+cu)^{2}}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/26ad71c0c04ec45f56779a3c0f74f8908c186286)
![{\displaystyle 0=p+l(a-n-1)+b(2an+2a-n^{2}-2n-2)-m}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/e8d7f3796b3d93fd66a0d8e105d852a6de58c62f)
![{\displaystyle 0=q+y(a-p-1)+s(2ap+2a-p^{2}-2p-2)-x}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/3fada9177227cf9fbe31cbde434113d334a5964b)
![{\displaystyle 0=z+pl(a-p)+t(2ap-p^{2}-1)-pm.}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/99f6316623f134275d3ce0ba5aa2d903b4bf10ff)
对于这个方程组的所有正整数解:(a,b,...,z),k + 2都是素数。可以把这个公式改写成多项式的形式:将14个等式记作p1,p2,……,p14,那么可以说,多项式
的输入值(a,b,...,z)是正整数时,其值域的正值部分就是所有素数。
根据尤里·马季亚谢维奇的一个定理,如果一个集合能够被定义成一个丢番图方程的解集,那么就可以被定义为一个只有9个未知数的丢番图方程的解集。于是,素数集合可以被定义为一个只含10个变元的多项式的正值解集。然而,这个多项式的次数极大(在1045数量级),另一方面,也存在次数不超过4的多项式,未知数个数是58个。
利用高斯符号
,可以建立一些第n个素数的表达式:
第一个带高斯函数的素数公式由W. H. Mills在1947年构造。他证明了存在实数A使得数列
![{\displaystyle [A^{3^{n}}\;]}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/7d8d9edba014f6e79ce8cfc2e5297e9f4955b6dd)
中的每个数都是素数。最小的A称为米尔斯常数,如果黎曼猜想成立,它的值大约为:
(
A051021)。
这个素数公式并没有什么实际价值,因为人们对A的性质所知甚少,甚至不知道A是否为有理数。而且,除了用素数值逼近外,没有其他计算A的方法。
使用威尔逊定理,可以建立一些其他的素数公式。以下的公式也没有什么实际价值,大多数的素性测试都比它远为有效。
我们定义
![{\displaystyle \pi (m)=\sum _{j=2}^{m}{\frac {\sin ^{2}({\pi \over j}(j-1)!^{2})}{\sin ^{2}({\pi \over j})}}}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/3b06e1c49c6ce60c4d4588e2742ba1dc175bf9d0)
或者
![{\displaystyle \pi (m)=\sum _{j=2}^{m}\left[{(j-1)!+1 \over j}-\left[{(j-1)! \over j}\right]\right].}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/a3bbf8f8521e0714399eec2be8f91fb8fbac3d96)
这两种定义是等价的。π(m)就是小于m的素数个数。于是,我们可以定义第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 .}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/ca39c1e274dfe0e323680782576515e9958f65a7)
这个例子没有用到阶乘和威尔逊定理,但也大量应用了高斯函数(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 }](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/1070170103c19ffc84d520b1b0664f113aa1a860)
然后就有第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).}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/1f2480e789329376c59283de6fa45ee962b3790d)
另外一个素数公式由以下递推关系组成的数列,其前后项的差来定义:
![{\displaystyle a_{n}=a_{n-1}+\operatorname {gcd} (n,a_{n-1}),\quad a_{1}=7,}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/a38b12cfab435346dcbd08869b9bab9552f2beb1)
其中gcd(x, y)表示x和y的最大公约数。这个数列的开始几项an+1 - an是1, 1, 1, 5, 3, 1, 1, 1, 1, 11, 3, 1, 1 (OEIS数列A132199)。Rowlands (2008)证明了这个数列只含有一和素数。
![{\displaystyle f(n)=2+(2n!\;{\pmod {n+1}})}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/eb8183111c4f8bf72745bd31ed0a737768d9cdd9)
其中,素数2出现无限多次,其余的素数恰好出现一次。实际上,当n+1是素数p的时候,由威尔逊定理,
等于p-2,于是
,当n+1是合数的时候,
等于0,于是得到2。