素数公式
质数公式,又称素数公式,在数学领域中,表示一种能够仅产生质数的公式。即是说,这个公式能够一个不漏地产生所有的质数,并且对每个输入的值,此公式产生的结果都是质数。由于质数的个数是可数的,因此一般假设输入的值是自然数集(或整数集及其它可数集)。迄今为止,人们尚未找到易于计算且符合上述条件的质数公式,但对于质数公式应该具备的性质已经有了大量的研究。
多项式形式的素数公式
编辑可以证明,一个整系数多项式P(n),如果不是常数函数的话,不会是一个素数公式。证明很简单:假设这样的一个多项式P(n)存在。那么P(1)将是一个素数p。接下来考虑 的值。由于 ,对于任意整数k,我们有 ,从而 是p的倍数,但已然假设 是素数公式,所以 必须是素数,于是它就只能等于 。也就是说,对于任意的k, 都是多项式P(n) - p的一个根。但根据代数基本定理,一个非零的整系数多项式不可能有无穷多个根。故此,P(n)只能是常数函数。
应用代数数理论,可以证明更强的结果:不存在能够对几乎所有自然数输入,都能产生素数的非常数的多项式P(n)。
欧拉在1772年发现,对于小于40的所有自然数,多项式
的值都是素数。对于前几个自然数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):
对于这个方程组的所有正整数解:(a,b,...,z),k + 2都是素数。可以把这个公式改写成多项式的形式:将14个等式记作p1,p2,……,p14,那么可以说,多项式 的输入值(a,b,...,z)是正整数时,其值域的正值部分就是所有素数。
根据尤里·马季亚谢维奇的一个定理,如果一个集合能够被定义成一个丢番图方程的解集,那么就可以被定义为一个只有9个未知数的丢番图方程的解集。于是,素数集合可以被定义为一个只含10个变元的多项式的正值解集。然而,这个多项式的次数极大(在1045数量级),另一方面,也存在次数不超过4的多项式,未知数个数是58个。
带高斯符号的素数公式
编辑利用高斯符号 ,可以建立一些第n个素数的表达式:
Mills公式
编辑第一个带高斯函数的素数公式由W. H. Mills在1947年构造。他证明了存在实数A使得数列
中的每个数都是素数。最小的A称为米尔斯常数,如果黎曼猜想成立,它的值大约为: ( A051021)。 这个素数公式并没有什么实际价值,因为人们对A的性质所知甚少,甚至不知道A是否为有理数。而且,除了用素数值逼近外,没有其他计算A的方法。
威尔逊定理的利用
编辑使用威尔逊定理,可以建立一些其他的素数公式。以下的公式也没有什么实际价值,大多数的素性测试都比它远为有效。
我们定义
或者
这两种定义是等价的。π(m)就是小于m的素数个数。于是,我们可以定义第n个素数如下:
另一个用高斯函数的例子
编辑这个例子没有用到阶乘和威尔逊定理,但也大量应用了高斯函数(S. M. Ruiz 2000)。首先定义:
然后就有第n个素数的表达式:
递推关系
编辑另外一个素数公式由以下递推关系组成的数列,其前后项的差来定义:
其中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)证明了这个数列只含有一和素数。
其他公式
编辑其中,素数2出现无限多次,其余的素数恰好出现一次。实际上,当n+1是素数p的时候,由威尔逊定理, 等于p-2,于是 ,当n+1是合数的时候, 等于0,于是得到2。
参考资料
编辑- ^ PrimeGrid’s AP26 Search (PDF). [2015-03-07]. (原始内容存档 (PDF)于2020-09-21).