integer - 41semicolon/41semicolon.github.io GitHub Wiki

素数は任意の基数で素数

100という数字が特別な意味を持つように見えるのは私たちが10進で物事を考えているからであり、2進数で表すと100という整数は特別な意味を持つようには見えない。片や素数はそうではない。素数はどの基数での表現しても素数でありその数学的な性質は変わらない。素数という性質は基数の取り方に依存しない普遍的な性質であると言える。

素数は整数の基本要素

任意の整数は素数の積として一意に因数分解できる。このことは、素数を素材に任意の整数を生み出すことができる、というように捉えることもできる。つまり、素数は整数界の原子であると言える（この例だと非素数は分子）

素数の個数は無限

背理法で示す。素数の一覧 {pi} があった時に Πpi + 1 はどの素数でも割りきれず、{pi} に含まれないので矛盾が示せる。

新たな素数の生成方法

知られていない。上述の Πpi + 1 がそれに当たりそうだが、さにあらず。世界記録はメルセンヌ素数（すなわち 2 ** n -1 )である。もちろん、全ての n に対して、 2 ** n -1 が素数になるわけではない。

素数の判定方法

知られていない。しかし、フェルマーの判定法を通過したならば、かなりの確率で素数であるといえる。すなわち、p が素数かどうかを判定したい場合、p よりも小さい n を任意に選び、 n ** p ≡ n (mod p) という素数の性質を満たすかどうかをチェックする。

素数を列挙

小さい順に素数を列挙するというユースケースはある。エラトステネスのふるいというアルゴリズムが使える。とはいえ、この方法では計算量が膨大になりすぎてあまり遠くにいけない。

素数の分布

素数定理で示される。ざっくり言うと100くらいまでは 4個に1個くらいの割合で素数が分布しているが、1000万くらいになると、17個に1個くらいの割合で分布する。要は段々と素数の分布はまばらになる。

素数の分布の偏り

リーマン予想と呼ばれる。素数定理で示される分布が局所的に適用できない区間があるか？という話。つまり予想される分布と比べて、素数が密集していたり、素数が疎に分布していたりする区間があるか？ということ。リーマン予想ではそんなことはない、とされている。

素数なしの区間を見つける

任意のn に対して、n-1 個連続して素数が出現しない区間を見つける方法がある。具体的には、[n!+2, n!+3, ... n!+n] である。この数列の i番目の要素は i で割り切れるため素数でない。

素数とフィボナッチ数

素数とフィボナッチ数には関係があるとされている。pが素数ならばp番目のフィボナッチ数は素数であることが多い。必ずこの性質が成り立つのであれば、素数生成機として使えるが、残念ながらそうではない。

素数の小話

素数ゼミ。異星人とのコミュニケーション（M13星団）。