- InxPVKTIOyOM4vu
- 3503
- 2
- 0
- 95
今日はどこで切っても素数だな: 20190823 => 素数 0190823 => 素数 190823 => 素数 90823 => 素数 0823 => 素数 823 => 素数 23 => 素数 3 => 素数
2019-08-23 10:06:01素数
@reoring @mrkn @kirito37652121 素数判定ってNP完全問題という計算がめちゃくちゃ大変な問題じゃありませんでしたっけ。 まあ、8桁程度ならパソコンレベルでも現実的な時間で計算可能ですが。
2019-08-23 18:22:51@mrkn 1の位が3だと、33,63,93以外は素数。 下二桁が23だと、4桁の数字は、2323, 4623,9223以外は素数? 下四桁が0823だと、、、 みたいなな形で、一般化すれば、わりと素数って見つかるかも。
2019-08-23 11:35:48@mrkn あ、これを、2進数でやると、案外素みつけるのが簡単なアルゴリズムみつからないかな。桁が倍々に増えていくからすぐに大きな素数が見つかったりしたら、すごいかも。
2019-08-23 11:44:19@mrkn えっとある素数pが、二進数でn桁で表現されるとしたら、下n桁がpである 2n桁の数のうち、2^n x p + p 以外は全部素数、っていう定理になるんだろうけれど、本当かな。
2019-08-23 12:01:17@mrkn ちょっと変形。 pが素数で、 2^n < p < 2^(n+1) であるとき 2^(n+1) + p は素数である。 たぶん、非効率的なエラトステネスの篩になっている18族元素。
2019-08-23 13:28:56あ、これは反例出てこないな。どっかで知られている定理だろうし。 pが素数で、2^n < p <2^(n+1) だと、2^(n+1) + p は、2pより小さいから。
2019-08-23 14:07:57@yuui_nesya ですです。15はすぐきがつきました。証明できないです。 正しくは、 pが素数で、 2^n < p < 2^(n+1) のとき、 2^n + p は素数。ですね。自明ですが。
2019-08-23 14:35:59@ryo_haibala 今日の日付を一桁ずつ削って素数かどうかチェックするスクリプトを AWS Lambda で毎朝実行して結果を Slack に流しています。
2019-08-23 13:19:01