【素数判定】自然数の分解に基づく素数判定遊び【Python】
事始め
覚えてないですよね^_^一昨年あたりに数学デーでひたすら僕のアマチュア数学研究テーマを書き連ねて説明してた奴です^_^
— ひさぴょん@勉強垢 (@o_hisashi) 2021年9月18日
式としてはこんなのです。
53=2^2×3×5-7
67=2×5×7-3
一目で素数ってわかるよね?ってやつ。
上記のひさぴょんさんの素数判定法が面白かったので、インスピレーションが湧いた。
397の素数判定式
397は一つの都合のいい素数の和差積であらわすことができないことが考えられているそうだ。ツイート内の引RT内の文献参照のこと。
そこで、2つの素数の和差積で表すことにして、実際成功した。
√397<20に注意して、
— FoxQ@楕円曲線を囲む会@表現者@物理学者@フォロバ99% (@foxq0113) 2021年9月18日
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
インスピレーションを受けて
今回の手法のポイントは2つの和か差の数に分けて、各数が多くの素数の積になっていて、なおかつそれら2数が互いに素であるということである。つまり、ツイートにまとめたように、
Nがk種類の素因数を持つ期待値をP(N)と書いた時、
— FoxQ@楕円曲線を囲む会@表現者@物理学者@フォロバ99% (@foxq0113) 2021年9月18日
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)で近似できるかな……
のように見積もれることになる。
実装
乱数で素数判定の式を2つに分けて、素因数の種類はなるべく大きくなるように更新すると、以下のようなプログラムになる。
2~10までの素数判定および素因数の種類数を既知として、10~1000までの素数判定を行った結果が次のものである。
gistf734d8d9838e28e061a878ce13489e0c
合成数と素数の判定成功率は約47%で、素数だけで判定成功確率を見ると約55%となっている。また、素因数の種類の推測値も同時にプロットされている。図では、値が1のところが正しく判定できている。
今回のケースは、1~1000までに素数は、168個あり、その内90個の判定に成功している。
1~1万までの数を対象に素数判定しても、合成数と素数の判定成功率は約49%で、素数だけで判定成功確率を見ると約56%となり、数の大きさの増加に対してある程度安定性があることがわかった。
このケースは、1~1万までに素数は、1229個あり、その内680個の判定に成功している。
まとめ
今回の推論モデルは、素因数の種類を確率的に見積もることで、そこから素数判定を行うものだった。成功確率は安定して55%付近となっており、素数の個数が減ってきても判定にはさほど影響を及ぼさないことが分かった。
【Kindle】因数分解と素因数分解【素因数分解】
Amazon.co.jp: Yoshiki Ueoka:作品一覧、著者略歴
対象読者は中学生1年生以上です。
九九の表をじっくりと観察することで、素数がなんなのか自然とわかるように解説しました。その後は、素数と素因数分解についてじっくり解説し、mod算まで解説しています。
本の最後には、RSA暗号について解説しています。
学校で習う数学や算数が世の中の役に立っていることを味わっていただきたいです。
【Python】N進数の和と積の表
N進数の和と積の表
九九から連想してN進数の和と積の表を作りたくなったので、作ってみた。
プログラム
0始まりなのは仕様です。Nの値を書き変えることでN進数にできます。デフォルトは16です。
gistee8bf0eeaad050831be763a3c1e26e14
【7×7=61】8進数と16進数の九九【f×f=e1】
8進数の足し算とかけ算の表
16進数の足し算とかけ算の表
倍数判定法
表を作っただけでは物足りないので、倍数判定法も。証明は10進数の時と同じです。
8進数で7の倍数か判定する方法
=各位を足した数が7で割り切れたら7の倍数
16進数で、3,5,fの倍数か判定する方法
=各位を足した数が3,5,fで割り切れたら3,5,fの倍数
8進数で2の倍数
=1の位が0,2,4,6
16進数で2の倍数
=1の位が0,2,4,6,8,a,c,e
8進数で4の倍数
=1の位が0か4
16進数で4の倍数
=1の位が0,4,8,c
16進数で8の倍数
=1の位が0か8
【確率】僕と同じ種類の人間はいるのか?【ドッペルゲンガー、そっくりさん】
仮定
各事象は計算の簡便のため独立とします。
確率
博士号取得*2
彼女がいる(18~39歳)*5
兼業研究者*6
自営業*7
作家を志す*8
数学者(プロ・アマ合算)
物理学者(概算)
障害年金受給者
ゲーマー*15
マンガを読む*16
ボカロ曲を歌う*17
旧帝卒*18
IQ145以上*19
数学検定2級*21
高校生のときに英検2級*22
僕が存在する確率
なんとプランク定数の倍だ。
人類は700万年前に誕生したので、単純計算67億人をかけると、上から、となる。
つまり、歴史上僕と同じ人はいなかっただろうことになる。それどころか後、年は同じ人は現れない計算になる。これは、地球の寿命*23の倍の時間である。
宇宙の寿命*24の倍の時間である。つまり、宇宙開闢が回程繰り返さないと僕みたいな人間は現れない。もうすでに唯一の存在になってしまったようだ。実は、正法眼蔵*25をそれなりに読んだなどもいれると、もっと確率は下がるが、さすがにマニアックなので省いた。
僕が存在する確率(高めの見積もり)
念のため、一般的な資格や趣味を取り除いて計算し直してみよう。以下の確率の積となる。
博士号取得
体が男のXジェンダー
彼女がいる(18~39歳)
兼業研究者
物理学者(概算)
自営業
作家を志す
男性イラストレーター(30~34歳)
IQ145以上
合計は、
ボーア磁子*26の程度となる。
人類は700万年前に誕生したので、単純計算67億人をかけると、上から、となる。
つまり、歴史上僕と同じ人はいなかっただろうことになる。それどころか後、年は同じ人は現れない計算になる。これは、地球の寿命*27から計算すると、僕と同じような人は、5人現れる可能性がまだある。ひょっとすると、輪廻転生があると仮定するなら、後僕が、4回ほど生まれ変わって、再び僕のような存在になるという意味かもしれない。だとしたら、僕が僕らしく生きられる可能性は、輪廻転生を仮定しても、もうあまり残されていない。
世界には、ドッペルゲンガーは3人いるといわれていて*28、また単純にそっくりさんもだいたい平均して3人いるらしい*29。しかしながら、上の確率から計算すると、僕が生きている間に、そっくりさんに出会う確率は、寿命を100歳としても、となる。つまり、僕に関しては、同年代に生きるドッペルゲンガーやそっくりさん存在仮説はほぼ否定されたことになる。
また、コンタクト可能な知的生命体レベルの文明の数は10個*30といわているので、僕が、僕と同じような生命体とコンタクトする確率は、寿命を100歳として、となる。
結局、僕が生きている間には、僕と同じような存在に出会うことは宇宙を探してもいなさそうだということになる。
今後も独創的な活動を続けていき、ますます宇宙一唯一無二の存在を目指していきたい。
おまけ:同じ悩みを抱える人はどれくらいいるか?
LGBTQ*31
自営業
IQ145以上
理系(なので話が合わない)
確率の積は、。
日本の人口をかけると、約31人となる。つまり、同じような境遇で苦しんでる人は、日本に31人くらいいるのでなんとかして出会いたい。
また、自営業と精神疾患を除くと、確率の積は、。
日本の人口をかけると、約6651人となる。つまり、同じような境遇の人でか関わってみたいは、日本に6651人くらいいるのでまだ希望が持てる。twitter経由で出会える可能性のある人数は*33、約1660人となる。僕の現在のフォロワーさんが4300人程度なので、ゆるく見て同じ境遇の人がフォロワーにいる確率は、約22%となる。だが、実際のところは、フォロワーに偏りがあり、ここまで確率は高くないだろう。
LGBTQさんでIQ145以上の人口の割合ならば、確率の積は。
twitterをアクティブにやっている人は、この内、おおざっぱに見積もって、2426人となる。
LGBTQさん限定でフォロワーさんを探すとなると、この内理系またはIQ145以上の人がいる確率は、30%となる。LBGTQさんを探していけば、目的の人といつかは関われそうだ。
*1:
*2:
*3:
https://www.pref.nagasaki.jp/shared/uploads/2020/02/1582270588.pdf
*4:
うつ病の患者数 | うつ病の情報・サポートサイト こころの陽だまり
*5:
「恋人いない30代」20年前の2倍に...東大の調査で分かった日本男女の“交際事情”[東京カレンダー]
*6:
*7:
日本における経営者・自営業者の割合とは? – 中小企業のデータ分析・活用支援ならKUROCO
*8:
*9:
https://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1317-22.pdf
*10:
*11:
https://www.mhlw.go.jp/topics/bukyoku/nenkin/nenkin/toukei/nenpou/2008/dl/gaiyou_h29.pdf
*12:
https://mugenup.com/wp-content/uploads/2020/01/8cd93b9c8dd7c2d5d7401440b7568642.pdf
*13:
日本人はプログラマ何人に1人くらい? - プログラマーなら60... - Yahoo!知恵袋
*14:
KONAMI、『遊戯王 デュエルリンクス』が全世界1億DL突破! 高橋和希先生描き下ろしの貴重なアクセサリーなど豪華プレゼントを予定 | gamebiz
*15:
*16:
*17:
https://www.t-kougei.ac.jp/static/file/vocaloid.pdf
*18:
高学歴の割合は何%!? 同世代の人口から分析! | たくみっく
*19:
IQ130と120の人と110と100の人はそれぞれ人口の何パーセン... - Yahoo!知恵袋
*20:
平成30年度 受検データ | 調査・データ | 日本漢字能力検定
漢検1級を持っている人って日本の人口の何%ですか? - 統計による1級所... - Yahoo!知恵袋
*21:
検定に関する各種データ | 数学検定・算数検定(実用数学技能検定)
*22:
高校生のうちに英検二級とれる人は全体の何パーセントくらいですか? ... - Yahoo!知恵袋
*23:
地球はあと何年でなくなるの,地球の寿命ってあるの | 自然 | 科学なぜなぜ110番 | 科学 | 学研キッズネット
*24:
宇宙の余命は1400億年以上 暗黒物質の分析で東大など将来予測 数百億年説を否定 - 産経ニュース
*25:
*26:
*27:
地球はあと何年でなくなるの,地球の寿命ってあるの | 自然 | 科学なぜなぜ110番 | 科学 | 学研キッズネット
*28:
ドッペルゲンガーで、自分にそっくりな人がこの世に3人いて、それを... - Yahoo!知恵袋
*29:
「自分にそっくりな人は世界に3人いる」が科学で証明される。3人どころかもっと多い可能性は高い(米研究) : カラパイア
*30:
*31:
LGBTの割合がバラつく理由【13人に1人? 100人に1人?】 | LGBT就活・転職活動サイト「JobRainbow」
*32:
https://www.mhlw-houkatsucare-ikou.jp/guide/h30-cccsguideline-p1.pdf
*33: