【素数判定】自然数の分解に基づく素数判定遊び【Python】

事始め

覚えてないですよね^_^一昨年あたりに数学デーでひたすら僕のアマチュア数学研究テーマを書き連ねて説明してた奴です^_^
式としてはこんなのです。

53=2^2×3×5-7
67=2×5×7-3

一目で素数ってわかるよね？ってやつ。
— ひさぴょん@勉強垢 (@o_hisashi) 2021年9月18日

上記のひさぴょんさんの素数判定法が面白かったので、インスピレーションが湧いた。

397の素数判定式

397は一つの都合のいい素数の和差積であらわすことができないことが考えられているそうだ。ツイート内の引RT内の文献参照のこと。

そこで、２つの素数の和差積で表すことにして、実際成功した。

√397＜20に注意して、

397=2^3×11×19-3×5^2×17⇒2,3,5,11,17,19の倍数でない。
397=2^2×7×13+3×11⇒2,3,7,11,13の倍数でない。

よって、397は素数。
式2つまで減らせた。 https://t.co/K3iwZoSPBm
— FoxQ@楕円曲線を囲む会@表現者@物理学者@フォロバ99% (@foxq0113) 2021年9月18日

インスピレーションを受けて

今回の手法のポイントは２つの和か差の数に分けて、各数が多くの素数の積になっていて、なおかつそれら2数が互いに素であるということである。つまり、ツイートにまとめたように、

Nがk種類の素因数を持つ期待値をP(N)と書いた時、
N=M±Lで、gcd(M,L)=1とする。
このとき、Nが素数になる確率p(N)は、
p(N)=(P(M)+P(L))/(√N以下の素数の個数)
=(P(M)+P(L)))/π(√N)
と見積もれる。後は、P(N)はπ(√N)-P(M)-P(L)で近似できるかな……
— FoxQ@楕円曲線を囲む会@表現者@物理学者@フォロバ99% (@foxq0113) 2021年9月18日

のように見積もれることになる。