素数の公式

数論において、素数の公式とは、素数を正確に例外なく生成する公式です。素数を計算する公式は存在しますが、計算に非常に時間がかかります。そのような「公式」が何であるか、何であるかを示す制約が数多く知られています。

簡単な式は

${\displaystyle f(n)=\left\lfloor {\frac {n!{\bmod {(}}n+1)}{n}}\right\rfloor (n-1)+2}$

正の整数 に対して、 は最も近い整数に切り捨てる床関数です。ウィルソンの定理により、が素数となるのは の場合のみです。したがって、が素数の場合、積の最初の因数は 1 になり、式は素数 を生成します。しかし が素数でない場合は、最初の因数は 0 になり、式は素数 2 を生成します。 ^[1]この式は、 を評価するには を法とする約数の乗算と約分が必要になる ため、素数を生成する効率的な方法ではありません。 ${\displaystyle n}$${\displaystyle \lfloor \ \rfloor }$${\displaystyle n+1}$${\displaystyle n!\equiv n{\pmod {n+1}}}$${\displaystyle n+1}$${\displaystyle n+1}$${\displaystyle n+1}$${\displaystyle n!{\bmod {(}}n+1)}$${\displaystyle n-1}$${\displaystyle n+1}$

1964年、ウィランズは

${\displaystyle p_{n}=1+\sum _{i=1}^{2^{n}}\left\lfloor \left({\frac {n}{\sum _{j=1}^{i}\left\lfloor \left(\cos {\frac {(j-1)!+1}{j}}\pi \right)^{2}\right\rfloor }}\right)^{1/n}\right\rfloor }$

番目の素数に対してです。^{[2]この式は[3] [4]} に簡約されます。つまり、この式はトートロジー的に、素数計算関数が少なくともnである最小の整数m をとして定義します。この式も効率的ではありません。 の出現に加えて、のコピーを加算することによって計算されます。たとえば、 です。 ${\displaystyle n}$${\displaystyle p_{n}}$ ${\displaystyle p_{n}=1+\sum _{i=1}^{2^{n}}[\pi (i)<n]}$${\displaystyle p_{n}}$ ${\displaystyle \pi (m)}$${\displaystyle (j-1)!}$${\displaystyle p_{n}}$${\displaystyle p_{n}}$${\displaystyle 1}$${\displaystyle p_{5}=1+1+1+1+1+1+1+1+1+1+1+0+0+\dots +0=11}$

ハーバート・ウィルフ（1982年）^[5]の論文「答えとは何か？ 」とアンダーウッド・ダドリー（1983年）^[6]の論文「素数の公式」では、このような公式の無価値についてさらに議論されています。

素数の集合は計算可能列挙集合であるため、マティヤセビッチの定理により、ディオファントス方程式のシステムから得ることができる。ジョーンズら (1976) は、26 変数の 14 個のディオファントス方程式の明示的な集合を発見した。この方程式では、与えられた数k  + 2 が素数であるためには、その方程式の解が非負整数である場合に限られる。 ^[7]

${\displaystyle \alpha _{0}=wz+h+jq=0}$

${\displaystyle \alpha _{1}=(gk+2g+k+1)(h+j)+hz=0}$

${\displaystyle \alpha _{2}=16(k+1)^{3}(k+2)(n+1)^{2}+1-f^{2}=0}$

${\displaystyle \alpha _{3}=2n+p+q+z-e=0}$

${\displaystyle \alpha _{4}=e^{3}(e+2)(a+1)^{2}+1-o^{2}=0}$

${\displaystyle \alpha _{5}=(a^{2}-1)y^{2}+1-x^{2}=0}$

${\displaystyle \alpha _{6}=16r^{2}y^{4}(a^{2}-1)+1-u^{2}=0}$

${\displaystyle \alpha _{7}=n+\ell +v-y=0}$

${\displaystyle \alpha _{8}=(a^{2}-1)\ell ^{2}+1-m^{2}=0}$

${\displaystyle \alpha _{9}=ai+k+1-\ell -i=0}$

${\displaystyle \alpha _{10}=((a+u^{2}(u^{2}-a))^{2}-1)(n+4dy)^{2}+1-(x+cu)^{2}=0}$

${\displaystyle \alpha _{11}=p+\ell (a-n-1)+b(2an+2a-n^{2}-2n-2)-m=0}$

${\displaystyle \alpha _{12}=q+y(a-p-1)+s(2ap+2a-p^{2}-2p-2)-x=0}$

${\displaystyle \alpha _{13}=z+p\ell (a-p)+t(2ap-p^{2}-1)-pm=0}$

14 個の方程式α ₀、…、α _{13 は}、26 個の変数を持つ素数生成多項式不等式を生成するために使用できます。

${\displaystyle (k+2)(1-\alpha _{0}^{2}-\alpha _{1}^{2}-\cdots -\alpha _{13}^{2})>0.}$

つまり、

${\displaystyle {\begin{aligned}&(k+2)(1-{}\\[6pt]&[wz+h+j-q]^{2}-{}\\[6pt]&[(gk+2g+k+1)(h+j)+h-z]^{2}-{}\\[6pt]&[16(k+1)^{3}(k+2)(n+1)^{2}+1-f^{2}]^{2}-{}\\[6pt]&[2n+p+q+z-e]^{2}-{}\\[6pt]&[e^{3}(e+2)(a+1)^{2}+1-o^{2}]^{2}-{}\\[6pt]&[(a^{2}-1)y^{2}+1-x^{2}]^{2}-{}\\[6pt]&[16r^{2}y^{4}(a^{2}-1)+1-u^{2}]^{2}-{}\\[6pt]&[n+\ell +v-y]^{2}-{}\\[6pt]&[(a^{2}-1)\ell ^{2}+1-m^{2}]^{2}-{}\\[6pt]&[ai+k+1-\ell -i]^{2}-{}\\[6pt]&[((a+u^{2}(u^{2}-a))^{2}-1)(n+4dy)^{2}+1-(x+cu)^{2}]^{2}-{}\\[6pt]&[p+\ell (a-n-1)+b(2an+2a-n^{2}-2n-2)-m]^{2}-{}\\[6pt]&[q+y(a-p-1)+s(2ap+2a-p^{2}-2p-2)-x]^{2}-{}\\[6pt]&[z+p\ell (a-p)+t(2ap-p^{2}-1)-pm]^{2})\\[6pt]&>0\end{aligned}}}$

は 26 個の変数を持つ多項式不等式であり、素数の集合は、変数a、b、…、z が非負の整数にわたる ため、左辺が取る正の値の集合と同一です。

マティヤセビッチの一般定理によれば、ある集合がディオファントス方程式のシステムで定義される場合、それは 9 個の変数のみを持つディオファントス方程式のシステムでも定義できる。^{[8]したがって、上記のような素数生成多項式不等式は 10 個の変数のみで存在する。しかし、その次数は大きい (10 45}のオーダー)。一方、次数が 4 で 58 個の変数を持つ方程式の集合も存在する。^[9]

最初に知られているそのような公式はWHミルズ（1947）によって確立され、彼は実数 Aが存在し、

${\displaystyle d_{n}=A^{3^{n}}}$

それから

${\displaystyle \left\lfloor d_{n}\right\rfloor =\left\lfloor A^{3^{n}}\right\rfloor }$

はすべての正の整数nに対して素数である。^[10]リーマン予想が正しい場合、そのような最小のAは約 1.3063778838630806904686144926... （OEISのシーケンスA051021 ）の値を持ち、ミルズ定数として知られている。^[11]この値から、、、、... （OEISのシーケンスA051254 ）という素数が生じる。定数Aについてはほとんどわかっていない（有理数であるかどうかさえも）。この式に実用的な価値はない。なぜなら、そもそも素数を見つけずに定数を計算する方法が知られていないからである。 ${\displaystyle \left\lfloor d_{1}\right\rfloor =2}$${\displaystyle \left\lfloor d_{2}\right\rfloor =11}$${\displaystyle \left\lfloor d_{3}\right\rfloor =1361}$

この式の床関数については特別なことは何もありません。トートは、次のような 定数も存在することを証明しました。${\displaystyle B}$

${\displaystyle \lceil B^{r^{n}}\rceil }$

は に対しても素数表現となる。^[12]${\displaystyle r>2.106\ldots }$

の場合、定数の値は1.24055470525201424067 から始まります。生成される最初のいくつかの素数は次のとおりです。 ${\displaystyle r=3}$${\displaystyle B}$

${\displaystyle 2,7,337,38272739,56062005704198360319209,}$

${\displaystyle 176199995814327287356671209104585864397055039072110696028654438846269,\ldots }$

エルショルツはリーマン予想を仮定せずに、ミルズの関数に似た素数表現関数をいくつか開発した。例えば、 の場合、 はすべての正の整数 に対して素数である。同様に、 の場合、 はすべての正の整数 に対して素数である。^[13]${\displaystyle A=1.00536773279814724017\ldots }$${\displaystyle \left\lfloor A^{10^{10n}}\right\rfloor }$${\displaystyle n}$${\displaystyle A=3.8249998073439146171615551375\ldots }$${\displaystyle \left\lfloor A^{3^{13n}}\right\rfloor }$${\displaystyle n}$

ミルズの定理に似た、もう一つのテトレーション的に増加する素数生成公式は、EMライトの定理から来ている。彼は、もし

${\displaystyle g_{0}=\alpha }$そして

${\displaystyle g_{n+1}=2^{g_{n}}}$のために、${\displaystyle n\geq 0}$

それから

${\displaystyle \left\lfloor g_{n}\right\rfloor =\left\lfloor 2^{\dots ^{2^{2^{\alpha }}}}\right\rfloor }$

はすべての に対して素数である。^[14] ライトはそのような定数の最初の 7 桁を次のように与えている。 。この値から、素数、、および が生じる。は偶数なので、は素数ではない。しかし、、、、および は変化しないが、 は4932 桁の素数である。^[15]この素数列は の桁をさらに知らないとを超えて拡張できない。ミルズの公式と同様、同じ理由で、ライトの公式も素数を見つけるのに使用できない。 ${\displaystyle n\geq 1}$${\displaystyle \alpha =1.9287800}$${\displaystyle \left\lfloor g_{1}\right\rfloor =\left\lfloor 2^{\alpha }\right\rfloor =3}$${\displaystyle \left\lfloor g_{2}\right\rfloor =13}$${\displaystyle \left\lfloor g_{3}\right\rfloor =16381}$${\displaystyle \left\lfloor g_{4}\right\rfloor }$${\displaystyle \alpha =1.9287800+8.2843\cdot 10^{-4933}}$${\displaystyle \left\lfloor g_{1}\right\rfloor }$${\displaystyle \left\lfloor g_{2}\right\rfloor }$${\displaystyle \left\lfloor g_{3}\right\rfloor }$${\displaystyle \left\lfloor g_{4}\right\rfloor }$${\displaystyle \left\lfloor g_{4}\right\rfloor }$${\displaystyle \alpha }$

定数（OEISのシーケンスA249270）が与えられた場合、シーケンスを定義する ${\displaystyle f_{1}=2.920050977316\ldots }$${\displaystyle n\geq 2}$

ここで は床関数である。 に対して、は番目の素数に 等しくなり、 、 、 などと なる。 ^[16]論文で与えられた 初期定数は、式( 1 )が 番目の素数である 37 までの素数を生成するのに十分正確である。 ${\displaystyle \left\lfloor \ \right\rfloor }$${\displaystyle n\geq 1}$${\displaystyle \left\lfloor f_{n}\right\rfloor }$${\displaystyle n}$${\displaystyle \left\lfloor f_{1}\right\rfloor =2}$${\displaystyle \left\lfloor f_{2}\right\rfloor =3}$${\displaystyle \left\lfloor f_{3}\right\rfloor =5}$${\displaystyle f_{1}=2.920050977316}$${\displaystyle 12}$

すべての素数を生成するの正確な値は、急速に収束する級数で与えられる。${\displaystyle f_{1}}$

${\displaystyle f_{1}=\sum _{n=1}^{\infty }{\frac {p_{n}-1}{P_{n}}}={\frac {2-1}{1}}+{\frac {3-1}{2}}+{\frac {5-1}{2\cdot 3}}+{\frac {7-1}{2\cdot 3\cdot 5}}+\cdots ,}$

ここで は番目の素数であり、 は未満のすべての素数の積です。 の桁が多ければ多いほど、方程式 ( 1 )はより多くの素数を生成します。たとえば、100 未満の 25 個の素数を使用して、この数列の 25 項を使用して、次のより正確な近似値を計算できます。 ${\displaystyle p_{n}}$${\displaystyle n}$${\displaystyle P_{n}}$${\displaystyle p_{n}}$${\displaystyle f_{1}}$

${\displaystyle f_{1}\simeq 2.920050977316134712092562917112019.}$

この式( 1 )には100未満の素数が25個再び得られるのに十分な桁数があります。

上記のミルズの公式やライトの公式と同様に、より長い素数のリストを生成するには、初期定数のより多くの桁を知ることから始める必要があり、この場合、計算にはより長い素数のリストが必要になります。 ${\displaystyle f_{1}}$

2018年にサイモン・プラウフは 素数の公式 を予想した。ミルズの公式と同様に、それらは次の形式である。

${\displaystyle \left\{a_{0}^{r^{n}}\right\}}$

ここで、は最も近い整数に丸める関数です。たとえば、とを使用すると、113、367、1607、10177、102217...（OEISのシーケンスA323176）が得られます。0 から 1/2 までの特定の数ととを使用すると、Plouffe は 50 個の可能性のある素数（素数である確率が高い）のシーケンスを生成できることを発見しました。おそらく、この式が実際の素数の無限シーケンスを生成する ε が存在するでしょう。桁数は 501 から始まり、毎回約 1% ずつ増加します。^{[17] [18]}${\displaystyle \{\ \}}$${\displaystyle a_{0}\approx 43.80468771580293481}$${\displaystyle r=5/4}$${\displaystyle a_{0}=10^{500}+961+\varepsilon }$${\displaystyle r=1.01}$${\displaystyle \varepsilon }$

すべての整数nに対して素数となる、整数係数を持つ非定数多項式関数P ( n ) は存在しないことが知られています。その証明は次のとおりです。そのような多項式が存在すると仮定します。するとP (1) は素数pとなるので となります。しかし、任意の整数kについても、p自体でない限り、 も素数になることはできません ( pで割り切れるため) 。ただし、すべてのkに対して素数になる唯一の方法は、多項式関数が定数である場合です。同じ推論から、さらに強力な結果が示されます。ほとんどすべての整数nに対して素数となる非定数多項式関数P ( n ) は存在しません。 ${\displaystyle P(1)\equiv 0{\pmod {p}}}$${\displaystyle P(1+kp)\equiv 0{\pmod {p}}}$${\displaystyle P(1+kp)}$${\displaystyle P(1+kp)=P(1)=p}$

オイラーは1772年に初めて、二次多項式

${\displaystyle P(n)=n^{2}+n+41}$

は、40 個の整数n = 0、1、2、...、39 に対して素数であり、対応する素数は 41、43、47、53、61、71、...、1601 です。項間の差は 2、4、6、8、10... です。n = 40 の場合、平方数1681 が生成されます。これは 41 × 41 に等しく、n ≥ 0の場合のこの式の最小の合成数です。41 でn が割り切れる場合、 P ( n ) も割り切れます。さらに、P ( n ) はn ( n + 1) + 41と表記できるため、代わりに 41 でn + 1 が割り切れる場合、P ( n ) も割り切れます。この現象は、同じく暗黙的に 2 次であるウラム螺旋と類数に関連しており、この多項式はHeegner 数に関連しています。他のヒーグナー数に対応する、 （オイラーの幸運な数）に対する類似の多項式が存在します。 ${\displaystyle 163=4\cdot 41-1}$${\displaystyle p=2,3,5,11{\text{ and }}17}$

正の整数Sが与えられた場合、式n ² + n + cが常にSと互いに素となるようなc が無限に存在する可能性があります。整数c は負になる可能性があり、その場合、素数が生成されるまでには遅延が生じます。

ディリクレの等差数列の定理に基づいて、線形多項式関数は、aとb が互いに素である限り、無限に多くの素数を生成することが知られています（ただし、そのような関数は、 nのすべての値に対して素値を想定することはありません）。さらに、グリーン・タオの定理によれば、任意のkに対して、 0 からk − 1 までの任意のnに対して素数である性質を持つaとbのペアが存在します。 ただし、2020 年現在、このようなタイプの最もよく知られている結果は、k = 27 の場合です。 ${\displaystyle L(n)=an+b}$${\displaystyle L(n)=an+b}$^[update]

${\displaystyle 224584605939537911+18135696597948930n}$

0から26までのすべてのnに対して素数である。^{[19]無限個の値が素数であると仮定する、少なくとも2次の}一変数多項式 が存在するかどうかさえ分かっていない。ブニャコフスキー予想を参照。

もう一つの素数生成子は再帰関係によって定義される。

${\displaystyle a_{n}=a_{n-1}+\gcd(n,a_{n-1}),\quad a_{1}=7,}$

ここで、gcd( x , y ) はxとyの最大公約数を表します。差のシーケンスa _{n +1} − a _nは、1、1、1、5、3、1、1、1、1、11、3、1、1、1、1、1、1、1、1、1、1、1、23、3、1、1、1、1、1、1、1、1、1、1、1、1、1、1、1、1、1、1、1、1、1、1、1、1、1、1、1、1、1、1、1、1、1、1、1、1、1、1、1、1、1、1、1、1、1、1、1、1、1、1、1、1、1、1、1、1、47、3、1、5、3、... で始まります (OEIS のシーケンス A132199)。Rowland (2008) は、このシーケンスには 1 と素数のみが含まれていることを証明しました。しかし、gcd( n +1, an )の項は常に奇数であり、2に等しくなることはないため、この数列には素数がすべて含まれているわけではない。587は_、 1と異なる最初の10,000個の結果に現れない最小の素数（2以外）である。それにもかかわらず、同じ論文では、非効率的ではあるが、すべての奇数の素数が含まれていると推測された。^[20]

すべての素数だけを列挙する簡単なプログラムや、より効率的なプログラムが存在することに注意してください。したがって、このような再帰関係は、実用的というよりも、好奇心の問題です。

• 素数定理

• Regimbal, Stephen (1975)、「k 番目の素数の明示的な公式」、Mathematics Magazine、48 (4)、アメリカ数学協会: 230–232、doi :10.2307/2690354、JSTOR  2690354。
• A Venugopalan.素数、双子素数、素数の数、双子素数の公式。インド科学アカデミー数学科学紀要、第92巻第1号、1983年9月、pp. 49-52 正誤表

• Weisstein, Eric W.、「素数公式」（「素数生成多項式」）（MathWorld）