素数の公式について詳しく解説

導入

数学では、すべての素数を与える (または素数のみを与える) 正確な式の探索は一般に無駄であることが判明し、近似式に落ち着きました。このページには、得られたさまざまな結果がリストされます。

単純な正確な式

n番目の素数pn _、または素数の数を与える正確で単純な公式の夢

, π( n ) は、非常に早い段階でその分布の極端な不規則性に直面したため、あまり野心的ではない目標に落ち着きました。しかし、素数のみを与える式を検索しても、まったく期待外れであることが判明しました。したがって、すべての整数n 、またはほとんどすべてのnに対して素数のみを取る非定数多項式関数P(n)が存在しないことを示すのは簡単です。実際、無限に多くの素数値を取る次数> 1の多項式が存在するかどうかさえわかりません。

これはオイラーの指摘、つまり 2 次多項式の興味深い点を説明しています。

は、40 未満のすべての正の整数に対して素数です (もちろん、 nが 41 の倍数の場合、 P(n)も 41 の倍数になるため、素数ではありません)。さらに、41 は、多項式n ² + n + AがA − 1未満のすべてのnについて素数となる最大の整数Aです。これは類体理論を使用すると難しい結果であり、1967 年に初めて実証されました。

メルセンヌの式など、より一般的な関数を使用する他の式も検討されましたが、最も有名なのはフェルマーによって予想されたものです。

はすべてのnに対して素数です。ああ、これらの数 (現在はフェルマー数と呼ばれています) が実際に素数であれば、 , オイラーは、6 番目のF ₅が 641 で割り切れることを発見し、予想が台無しになりました。現在、私たちは逆に、 F _{n は}常にn > 4になるとすぐに構成されると考えており、同様に、素数のみを与えるミルズの理論式しか知りません… ただし、実際には、最後のセクションで説明するように、これは純粋に理論的なものです。

正確な数式…しかし実用的ではありません

ただし、前述の説明にもかかわらず、単純に見える正確な式を取得することは可能です。したがって、ウィルソンの定理を使用すると、次の関数が簡単に示されます。

n がすべての正の整数を通過する場合、すべての素数のみを生成します。 n + 1が合成の場合はf ( n ) = 2 、n + 1 が素数の場合はf ( n ) = n + 1 となります。 mod 関数の使用には問題はありません。なぜなら、それを素早く計算する方法がわかっているからです。一方、 nの階乗はすぐに実際には使用できないほど大きすぎる値になります。さらに、この関数は実際にはπ( n )を与えるのではなく、 nが素数であるかどうかをテストするだけであり、約n回の基本演算を計算する必要があるため、この目的では単純な除算方法よりもはるかに非効率的です。すべての整数 、それ自体は現在知られている最良の素数テストよりもはるかに遅いです。

p _nまたはπ( n )を直接与える他の式は、 fから構築できます。したがって、整数部関数を使用すると、次のようになります。

$$ { \pi(m) = \sum_{j=2}^m \left[ {(j-1)! + 1 \over j} – \left[{(j-1)! \over j}\right] \right]} $$

;

しかし、これらの式は明らかに、 f を与える式よりもさらに使いにくくなります。

ウィルソンの定理を使用しない、より有望な別のアプローチは、本質的に、エラトステネスのふるい、またはそこから演繹できるルジャンドルの包含排除公式などの公式を「シミュレートする」ことで構成されています。この地形は多くのアマチュアのお気に入りの地形であるため、2000 年にスペイン語教師 SMRuiz によって次の公式が決定されました。

$$ {\pi(k) = k – 1 + \sum_{j=2}^k \left[ {2 \over j} \left(1 + \sum_{s=1}^{\left[\sqrt{j}\right]} \left(\left[{ j-1 \over s}\right] – \left[{j \over s}\right]\right) \right)\right] } $$

そして

$$ {p_n = 1 + \sum_{k=1}^{2([ n \ln(n)]+1)} \left(1 – \left[{\pi(k) \over n} \right]\right). } $$

これらの式には多数の合計があることに気づくでしょう。これは、これらも実際にはほとんど役に立たないことを意味します。 π( n )と_pnを正確に計算するためのより優れた方法は、これらの関数に関する記事で詳しく説明されていますが、依然として比較的効果が低いです。

最初のセクションの指摘を考慮すると、素数値のみを取るいくつかの変数を含む多項式の存在はありそうもないように思えましたが、また、マティアセビッチの研究（1970年）でも、ディオファントス関係はそのような多項式によって「コード化」できることが示されました。 、本当に驚きを引き起こしました。この結果の明確な例を示すことも可能です。したがって、次のような巨大な多項式 (26 個の変数で構成され、次数 25) になります。

(k+2)[1 – (wz+h+j–q) ² – [(gk+2g+k+1)(h+j) + h – z] ² – (2n+p+q+z– e) ² – [16(k+1) ³ (k+2)(n+1) ² + 1 – f ² ] ² – [e ³ (e+2)(a+1) ² + 1 – o ² ] ² – [(a ² –1)y ² + 1 –x ² ] ² – [16r ² y ⁴ (a ² –1) + 1 – u ² ] ²

– [((a+u ² (u ² –a)) ² –1)(n+4dy) ² + 1 – (x+cu) ² ] ² –[n+l+v–y] ² – [( a ² –1)l ² + 1 – m ² ] ² – [ai+k+1–l–i] ² – [p + l(a–n–1) + b(2an+2a–n ² –2n –2) – m] ² – [q+ y(a–p–1) + s(2ap + 2a – p ² – 2p – 2) – x] ²

– [z + pl(a–p) + t(2ap – p ² – 1) – pm] ² ]

a、正の値のセットの場合、正確に素数のセット。しかし、私たちはこれらが依然として「公式」なのかどうか疑問に思うかもしれません。かなり似たような流れで、コンウェイはシラキュース問題の一般化を定義し、それを プログラミング言語FRACTRAN に変換しました。次のテキスト:

$$ {\frac{17}{91}, \frac{78}{85}, \frac{19}{51}, \frac{23}{38}, \frac{29}{33}, \frac{77}{29}, \frac{95}{23}, \frac{77}{19}, \frac{1}{17}, \frac{11}{13}, \frac{13}{11}, \frac{15}{14}, \frac{15}{2}, \frac{55}{1}.} $$

この言語の場合、これは素数のシーケンスを順番に生成するプログラムに相当します。これは、少なくとも先行するものと同じくらい洗練された式とみなすことができます。

最後に、ミルズは、任意の整数nに対して、次のような実数M が存在することを示しました。

または素数。この性質を持つ最小のMであるミルズ定数も、高い精度で知られています…これは、実際に大きな素数を計算する場合と同様に幻想的であることがわかります。 p (25) を格納するには、すでにテラバイトが必要です)。