質數公式,又稱素數公式,在數學領域中,表示一種能夠僅產生質數的公式。即是說,這個公式能夠一個不漏地產生所有的質數,並且對每個輸入的值,此公式產生的結果都是質數。由於質數的個數是可數的,因此一般假設輸入的值是自然數集(或整數集及其它可數集)。迄今為止,人們尚未找到易於計算且符合上述條件的質數公式,但對於質數公式應該具備的性質已經有了大量的研究。
可以證明,一個整系數多項式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。