利用者:Hrtauo/素数の公式

aaaaaa数論で、素数の公式は正確に素数を生成する公式である。効率的に計算できるそのような式は知られていない。素数の公式にはいくつかの条件が知られており、そのような公式に何ができるか、何ができないかを示している。

ウィルソンの公式

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

($n$は正の整数で 、 $\lfloor \ \rfloor$は床関数である。）この式は、ウィルソンの定理により、 $n+1$が素数である場合に$n!\equiv n{\pmod {n+1}}$ なので素数であり、$n+1$が素数の時、この式の出力は素数になる 。でも$n+1$が素数ではない場合、式は2を出力する。 この式は素数を効率良く生成できません。$n+1$を法として $n!$と$n-1$が合同でない必要があります。

1964年、ウィランスは次の式を発見した。

$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$

$n$が正の整数の時、$p_{n}$は素数になる 。 この式も効率的ではありません。$p_{n}$の総和を計算することによって$p_{n}$が得られます。例1:例えば、 $p_{5}=1+1+1+1+1+1+1+1+1+1+1+0+0+\dots +0=11$

ディオファントス方程式に基づく式

素数の集合は計算可能に列挙可能な集合であるため、マチャセビッチの定理により、ディオファントス方程式から取得できます。Jones et al. (1976)与えられた数kのように、26の変数から成る14のディオファントス方程式の明示的な集合を見つけました。 この方程式は、そのシステムに自然数の解がある場合にのみ素数になります

$\alpha _{0}=wz+h+j-q=0$

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

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

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

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

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

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

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

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

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

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

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

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

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

14個の方程式α0 、…、 a13を使用して、26個の変数で素数を生成する多項式の不等式を生成できます。

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

すなわち：

${\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つの変数のみのディオファントス方程式の定義によっても定義できます。 したがって、上記のように10個の変数のみを持つ素数生成多項式があります。ただし、その程度は大きいです（10 ⁴⁵のオーダー）。一方、次数4の方程式も存在しますが、58個の変数があります。

ミルズの公式

知られている最初のそのような公式はW. H. Mills ([[#CITEREFMills|]])によって確立されました 、実数Aが存在することを証明した人は、

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

それから

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

はすべての正の整数nの素数です。 リーマン予想が真である場合、そのような最小のAの値は約1.3063778838630806904686144926 ...であり、ミルズ定数として知られています。$d_{n}$は素数になります。$\left\lfloor d_{1}\right\rfloor =2$ 、 $\left\lfloor d_{2}\right\rfloor =11$ 、 $\left\lfloor d_{3}\right\rfloor =1361$ 、... 定数Aについてはほとんど知られていません（有理数であるかどうかさえも）。そもそも素数を見つけずに定数を計算する既知の方法がないため、この式には実用的な価値が多くありません。

式の床関数については特別なことは何もないことに注意してください。 Tóth は、定数も存在することを証明しました。ある$B$が存在して

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

も素数を表します$r>2.106\ldots$ (Tóth 2017) 。

その場合($r=3$) 、定数$B$＝ 1.24055470525201424067...で始まります。 生成される最初のいくつかの素数は次のとおりです。

$2,7,337,38272739,56062005704198360319209,176199995814327287356671209104585864397055039072110696028654438846269,\ldots$

リーマン予想を仮定せずに、エルショーツはミルズのものと同様の複数個の素数関数を発見しました。たとえば、 $A\approx 1.00536773279814724017$ や などの時、$\left\lfloor A^{10^{10n}}\right\rfloor$はすべての正の整数$n$に対して素数になります 。同様に、 $A\approx 3.8249998073439146171615551375$の時$\left\lfloor A^{3^{13n}}\right\rfloor$はすべての正の整数$n$に対して素数になります 。

ライトの公式

ミルズの式に似た別の素数生成式は、 ライトの定理に由来します。彼はある実数αが存在することを証明しました。

$g_{0}=\alpha$と

$g_{n+1}=2^{g_{n}}$為に$n\geq 0$ 、

それから

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

はすべての$n\geq 1$に対して素数である 。 ライトは、$\alpha$の小数点以下7桁を求めました。 $\alpha =1.9287800$... 。この値は素数を生成します。 $\left\lfloor g_{1}\right\rfloor =\left\lfloor 2^{\alpha }\right\rfloor =3$、 $\left\lfloor g_{2}\right\rfloor =13$、$\left\lfloor g_{3}\right\rfloor =16381$ 。 $\left\lfloor g_{4}\right\rfloor$以降も素数になります。しかし、 $\alpha =1.9287800+8.2843\cdot 10^{-4933}$ 、 $\left\lfloor g_{1}\right\rfloor$ 、 $\left\lfloor g_{2}\right\rfloor$ 、 $\left\lfloor g_{3}\right\rfloor$は表記できますが、$\left\lfloor g_{4}\right\rfloor$は 表記できませんになります。 この素数の数列は拡張することはできません。$\left\lfloor g_{5}\right\rfloor$以降の項をが求められていないからです。そして同じ理由で、ライトの公式は素数を見つけるために使用することは多くありません。

すべての素数を表す関数

定数が与えられた$f_{1}=2.920050977316\ldots$ オンライン整数列大辞典の数列 A249270 関数 、 $n\geq 2$ について次の漸化式で$f_{n}$を定義します。

$f_{n}=\left\lfloor f_{n-1}\right\rfloor (f_{n-1}-\left\lfloor f_{n-1}\right\rfloor +1)$

(1)

($\left\lfloor \ \right\rfloor$は床関数。) 正の整数$n$について、$\lfloor f_{n}\rfloor$は素数になります。( $\left\lfloor f_{1}\right\rfloor =2$ 、 $\left\lfloor f_{2}\right\rfloor =3$ 、 $\left\lfloor f_{3}\right\rfloor =5$) 。初期定数は$f_{1}=2.920050977316$です。この記事で与えられているのは、この漸化式は37までの素数を生成するのに十分正確です。

この正確な値$f_{1}$すべての素数を生成するものは、急速に収束する級数によって与えられます

$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 ,$

$p_{n}$はそして$P_{n}$未満のすべての素数の積です 。私たちが知っているように、より多くの素数方程式（が生成されます。たとえば、100未満の25の素数を使用して、シリーズの25の項を使用して、次のより正確な近似を計算できます。

$f_{1}\simeq 2.920050977316134712092562917112019.$

これには、式（ 1 ）に十分な桁があり、100未満の25個の素数が再び生成されます。

上記のMillsの式とWrightの式と同様に、素数のより長いリストを生成するには、最初の定数のより多くの桁を知ることから始める必要があります。 $f_{1}$ 、この場合、計算に素数のより長いリストが必要です。

プルーフの公式

2018年、サイモン・プラウフは素数の公式を推測しました。ミルズの公式と同様に、それらは次の形式になります.

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

$\{\ \}$は最も近い整数に丸める関数です。たとえば、 $a_{0}\approx 43.80468771580293481$と$r=5/4$ 、これにより、113、367、1607、10177、102217...が得られます。使用する$a_{0}=10^{500}+961+\varepsilon$と$r=1.01$と$\varepsilon$ は、0から1/2の間の数で、50個の確率的素数を生成できることを発見しました。おそらく、この式が実際の素数の無限の素数を与えるようなεが存在します。桁数は501から始まり、毎回約1％ずつ増えていきます。

プライム式と多項式関数

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

オイラーは1772年に次の二次多項式を発見しました。

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

$P(n)$は整数n =0、1、2、...、39で素数でを生成し、対応する素数は41、43、47、53、61、71、...1601です。用語の違いは2、4、6、8、10...です。 n = 40の場合、平方数1681が生成されます。n=  41、 n≥0の場合のこの式の最小合成数。 nが41で割り切れるとすると、 P(n)も割り切れます。さらに、 P(n)はn(n + 1）+ 41、nが41で割り切れる場合、 P (n )も割り切れます。この現象は、暗黙的に2次式であるウラムの螺旋とクラス番号に関連しています。この多項式は、ヒーグナー数に関連していて、($163=4\cdot 41-1$ )この2次式に類似した多項式があります。$p=2,3,5,11{\text{ and }}17$ （オイラーの幸運数）、他のヘーグナー数に対応します。

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

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

$224584605939537911+18135696597948930n$

は、0から26までのすべてのnに対して素数です。 素数である値の数が無限であると仮定して、少なくとも2次の単変量多項式が存在するかどうかもわかりません。ブニャコフスキー予想を参照してください。

漸化式を使用した可能な式

別の素数を生成する式は次の漸化式によって定義されます。

$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で始まります。 、 ... 関数 。 ローランド (2008)は、このシーケンスには1と素数のみが含まれていることを証明しました。ただし、gcd（ n + 1、 a _n ）は常に奇数であるため、2に等しくなることはありません。587は、1とは異なる最初の10,000の結果に表示されない最小の素数（2を除く）です。それにもかかわらず、同じ論文では、それはかなり非効率的ですが、すべての奇数の素数を含むと推測されました。

素数だけを列挙する簡単なプログラムと、より効率的なプログラムがあることに注意してください。そのため、このような漸化式は、実際の使用よりも好奇心の問題です。

関連記事

• 素数定理

参考文献

• Regimbal, Stephen (1975), “An explicit Formula for the k-th prime number”, Mathematics Magazine (Mathematical Association of America) 48 (4): 230–232, doi:10.2307/2690354, JSTOR 2690354, https://jstor.org/stable/2690354 .
• A Venugopalan. Formula for primes, twinprimes, number of primes and number of twinprimes. Proceedings of the Indian Academy of Sciences—Mathematical Sciences, Vol. 92, No 1, September 1983, pp. 49–52 errata

外部リンク

• Eric W. Weisstein, Prime Formulas (Prime-Generating Polynomial) at MathWorld.