素数公式

维基百科,自由的百科全书
跳转至: 导航搜索

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

多项式形式的素数公式[编辑]

可以证明,一个多项式Pn),如果不是常数的话,不会是一个素数公式。证明很简单:假设这样的一个多项式Pn)存在,那么P(1)将是一个素数p。接下来考虑P(1+kp)的值。由于P(1) \equiv 0 \pmod p,我们有P(1+kp) \equiv 0 \pmod p 。于是P(1+kp)p的倍数。为了使它是素数,P(1+kp)只能等于p。要使得这对任意的k都成立,Pn)只能是常数。

应用代数数理论,可以证明更强的结果:不存在能够对几乎所有自然数输入,都能产生素数的非常数的多项式Pn)。

欧拉在1772年发现,对于小于40的所有自然数,多项式

P(n) = n2 - n + 41

的值都是素数。对于前几个自然数n = 0, 1, 2, 3……,多项式的值是41, 43, 47, 53, 61, 71……。当n等于41时,多项式的值是1681=41×41,是一个合数。实际上,当n能被41整除的时候,Pn)也能被41整除,因而是合数。这个公式和所谓的质数螺旋有关,也和黑格納數163=4\cdot 41-1有關。若p=2, 3, 5, 11, 17時,其對應的多項式也有類似的性質,而4\cdot p -1也是黑格納數。

狄利克雷定理证明了,对于互素ab, 线性多项式方程L(n) = an + b能产生无穷多个质数(尽管不是对于所有的自然数n)。此外,格林-陶定理证明了更强的结论:对于每个正整数k,都存在着整数对ab,使得对于每个0与k−1之间的nL(n) = an+b都是素数。然而,对于比较大的k,找出ab是很困难的。最好的结果是对于k=24,

P(n) = 45872132836530n + 468395662504823; [1]

至于是否存在次数大于等于2的多项式,满足对无穷多个整数,都能取到素数值,目前还没有结论。

丢番图方程形式的素数公式[编辑]

一个很著名的素数公式是以下的有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,...,z),k + 2都是素数。可以把这个公式改写成多项式的形式:将14个等式的右边记作p1,p2,……,p14,那么可以说,多项式 (k+2)(1-p_1^2-p_2^2-\cdots- p_{14}^2) 的输入值(a,b,...,z)是正整数时,其值域的正值部分就是所有素数。

根据尤里·马季亚谢维奇的一个定理,如果一个集合能够被定义成一个丢番图方程的解集,那么就可以被定义为一个只有9个未知数的丢番图方程的解集。于是,素数集合可以被定义为一个只含10个变元的多项式的正值解集。然而,这个多项式的次数极大(在1045数量级),另一方面,也存在次数不超过4的多项式,未知数个数是58个。

带高斯函数的素数公式[编辑]

利用高斯函数\lfloor x\rfloor,可以建立一些第n个素数的表达式:

Mills公式[编辑]

第一个带高斯函数的素数公式由W. H. Mills在1947年构造。他证明了存在实数A使得数列

\lfloor A^{3^{n}}\;\rfloor

中的每个数都是素数。最小的A=1.30637788386308069046……,称为米爾斯常數。这个公式并没有什么实际价值,因为人们对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\lfloor {(j-1)! + 1 \over j} - \left\lfloor{(j-1)! \over j}\right\rfloor \right\rfloor.

这两种定义是等价的。π(m)就是小于m的素数个数。于是,我们可以定义第n个素数如下:

p_n = 1 + \sum_{m=1}^{2^n}  \left\lfloor \left\lfloor { n \over 1 + \pi(m) } \right\rfloor^{1 \over n} \right\rfloor.

另一个用高斯函数的例子[编辑]

这个例子没有用到阶乘威尔逊定理,但也大量应用了高斯函数(S. M. Ruiz 2000)。首先定义:

\pi(k) = k - 1 + \sum_{j=2}^k \left\lfloor {2 \over j} \left(1 +  \sum_{s=1}^{\left\lfloor\sqrt{j}\right\rfloor} \left(\left\lfloor{ j-1 \over s}\right\rfloor - \left\lfloor{j \over s}\right\rfloor\right) \right)\right\rfloor

然后就有第n个素数的表达式:

p_n = 1 + \sum_{k=1}^{2(\lfloor n \ln(n)\rfloor+1)} \left(1 - \left\lfloor{\pi(k) \over n} \right\rfloor\right).

递推关系[编辑]

另外一个素数公式由以下递推关系組成的數列,其前後項的差來定义:

 a_n = a_{n-1} + \operatorname{gcd}(n,a_{n-1}), \quad a_1 = 7,

其中gcd(x, y)表示xy最大公因子。这个数列的开始几项an+1 - an是1, 1, 1, 5, 3, 1, 1, 1, 1, 11, 3, 1, 1 (OEIS中的数列A132199)。Rowlands (2008)证明了这个数列只含有一和素数。

其他公式[编辑]

威尔逊定理衍生公式[编辑]

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。

筛法的公式[编辑]

筛法的公式

参见[编辑]