素数公式

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

多项式形式的素数公式

可以证明,一个整系數多项式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整除,因而是合数。这个公式和所谓的质数螺旋有关,也和黑格納數 有關。若 時,其對應的多項式也有類似的性質,而 也是黑格納數。

狄利克雷定理证明了,对于互素ab線性函數 能产生无穷多个质数(尽管不是对于所有的自然数n)。至于是否存在次数大于等于2的多项式,满足对无穷多个整数,都能取到素数值,目前还没有结论。

此外,格林-陶定理证明了另一结论:对于每个正整数k,都存在着整数对a, b,使得对于每个0与k−1之间的n 都是素数。然而,对于比较大的k,找出ab是很困难的。目前最好的结果是对于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)表示xy最大公因數。这个数列的开始几项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。

參考資料

  1. ^ PrimeGrid’s AP26 Search (PDF). [2015-03-07]. (原始内容存档 (PDF)于2020-09-21). 

参见