テストスレ [無断転載禁止]©2ch.net (756ﾚｽ)
上下前次1-新
抽出解除 必死ﾁｪｯｶｰ(本家) (べ) 自ID ﾚｽ栞 あぼーん
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
613: １３２人目の素数さん [sage] 2023/11/12(日) 11:59:19.28 ID:yQVh9yuF(1/12) AAS
2017年現在では、5≤n≤32 に対して Fn が合成数であることが分かっている。 F20,F24 は合成数だが素因子は一つも見つかっていない。
https://www.math.kyoto-u.ac.jp/~yamasaki/a3f-ja.html
F(20)はPépinの判定法で素数と判定されなかったので合成数と判定されている模様。
F(20)を素数テーブルで割った余りが0になるループチェックが必要？
まぁF(20)の素因数は発見したら新発見なんだろうが誰かやるのか？
615: １３２人目の素数さん [] 2023/11/12(日) 12:45:57.77 ID:yQVh9yuF(2/12) AAS
test
616: １３２人目の素数さん [] 2023/11/12(日) 13:06:37.66 ID:yQVh9yuF(3/12) AAS
早速pythonのsympyでF20の素数判定と素因数抽出プログラムを作って流してみたが、実行時間がかかっている。
618: １３２人目の素数さん [] 2023/11/12(日) 14:55:44.23 ID:yQVh9yuF(4/12) AAS
以下の素数判定プログラムをcolabで流したところでは1時間程度では処理が終わらなかった。同時に流している素因数抽出プログラムはもっと時間がかかるだろうな。
```
import datetime
dt_now1 = datetime.datetime.now()
print(dt_now1)
from sympy import isprime
print(isprime((65536**65536)+1))
dt_now2 = datetime.datetime.now()
print(dt_now2)
print(dt_now2 - dt_now1)
```
仕方がないのでもっと小さい値から実行時間を計測しながらやり直してみる。
colabはセッションを2つまでしか同時実行できないので、1つ目の処理を止める。
619: １３２人目の素数さん [] 2023/11/12(日) 15:26:33.48 ID:yQVh9yuF(5/12) AAS
```
import datetime
dt_now1 = datetime.datetime.now()
print(dt_now1)
from sympy import isprime
print(isprime((65536**512)+1))
dt_now2 = datetime.datetime.now()
print(dt_now2)
print(dt_now2 - dt_now1)
```
で
0:00:02.865594
```
import datetime
dt_now1 = datetime.datetime.now()
print(dt_now1)
from sympy import isprime
print(isprime((65536**1024)+1))
dt_now2 = datetime.datetime.now()
print(dt_now2)
print(dt_now2 - dt_now1)
```
で
0:00:22.930379
うむ？
```
512 0:00:02.865594 3
1024 0:00:22.930379 23 9倍
2048 0:02:47.323848 167 7倍
4096 1336(予想) 8倍(予想)
8192 10688(予想) 8倍(予想)
16384 85504(予想) 8倍(予想)
32768 684032(予想) 8倍(予想)
65536 5472256(予想) 8倍(予想) 分だと91204分 時間だと1520時間 日数だと64日
```
・・・計算時間に64日かかるのであきらめる。
620: １３２人目の素数さん [] 2023/11/12(日) 15:56:38.89 ID:yQVh9yuF(6/12) AAS
ローカルにsympyを入れて実行したところcolabより8～64倍速く実行できた。
しかし4096で1分以上かかるので、65536では21～24時間程度かかることになる。
どうせfalseで合成数だろうし、素数ではなく合成数だと分かったところで素因数が分からないと意味がない。
もっと工夫しないといけない。
621: １３２人目の素数さん [] 2023/11/12(日) 16:23:17.54 ID:yQVh9yuF(7/12) AAS
F(0)=3:true
F(1)=5:true
F(2)=17:true
F(3)=257:true
F(4)=65537:true
F(5)=4294967297=(65536^2)+1:false
F(6)=18446744073709551617=(65536^4)+1:false
F(7)=340282366920938463463374607431768211457=(65536^8)+1:false
F(8)=115792089237316195423570985008687907853269984665640564039457584007913129639937=(65536^16)+1:false
F(9)=(65536^32)+1:false
F(10)=(65536^64)+1:false
F(11)=(65536^128)+1:false
F(12)=(65536^256)+1:false
F(13)=(65536^512)+1:false
F(14)=(65536^1024)+1:false
F(15)=(65536^2048)+1:false
F(16)=(65536^4096)+1:false
F(17)=(65536^8192)+1
F(18)=(65536^16384)+1
F(19)=(65536^32768)+1
F(20)=(65536^65536)+1
622: １３２人目の素数さん [] 2023/11/12(日) 17:00:44.59 ID:yQVh9yuF(8/12) AAS
F(0)=3:true
F(1)=5:true
F(2)=17:true
F(3)=257:true
F(4)=65537:true
F(5)=4294967297=(65536^2)+1:false:{641: 1, 6700417: 1}
F(6)=18446744073709551617=(65536^4)+1:false:{274177: 1, 67280421310721: 1}
F(7)=340282366920938463463374607431768211457=(65536^8)+1:false:{59649589127497217: 1, 5704689200685129054721: 1}
F(8)=115792089237316195423570985008687907853269984665640564039457584007913129639937=(65536^16)+1:false:{1238926361552897: 1, 93461639715357977769163558199606896584051237541638188580280321: 1}
F(9)から素因数抽出も時間がかかる。
とりあえずF(8)まで。
624: １３２人目の素数さん [] 2023/11/12(日) 22:09:09.47 ID:yQVh9yuF(9/12) AAS
ペピンの素数判定法によるF(20)の素数判定
3^( (((65536^65536)+1)-1) / 2 ) ≡ -1 (mod ((65536^65536)+1))
https://ja.wolframalpha.com/input?i=3%5E%28+%28%28%2865536%5E65536%29%2B1%29-1%29+%2F+2+%29+%E2%89%A1+-1+%28mod+%28%2865536%5E65536%29%2B1%29%29
偽
625: １３２人目の素数さん [] 2023/11/12(日) 22:12:06.72 ID:yQVh9yuF(10/12) AAS
ペピンの素数判定法によるF(1048596)の素数判定
3^( (((65536^65536)^(65536^65536)+1)-1) / 2 ) ≡ -1 (mod ((65536^65536)^(65536^65536)+1))
https://ja.wolframalpha.com/input?i=3%5E%28+%28%28%2865536%5E65536%29%5E%2865536%5E65536%29%2B1%29-1%29+%2F+2+%29+%E2%89%A1+-1+%28mod+%28%2865536%5E65536%29%5E%2865536%5E65536%29%2B1%29%29
偽
626: １３２人目の素数さん [] 2023/11/12(日) 22:13:58.84 ID:yQVh9yuF(11/12) AAS
F(5)以降のフェルマー数は全部合成数なんじゃね？
つまりフェルマー素数は5個しか無いんじゃね？
627(1): １３２人目の素数さん [] 2023/11/12(日) 22:16:14.39 ID:yQVh9yuF(12/12) AAS
ペピンの素数判定法とは？
ペピンの素数判定法は、フェルマー数が素数であるかどうかを判定するための方法です³。具体的には、nが1以上のとき、次の等式が成り立つことがフェルマー数F(n)が素数であるための必要十分条件となります³:
3^( (F(n)-1) / 2 ) ≡ -1 (mod F(n))³
この判定法は、フェルマー数に対する有効な素数判定法の一つです¹²。ただし、フェルマー数以外の数に対しては、この方法は適用できません¹²。
ソース: Bing との会話 2023/11/12
(1) 素数の判定（ペパン判定法） - 単なるリンクのメニュー. https://bing.com/search?q=%e3%83%9a%e3%83%94%e3%83%b3%e3%81%ae%e7%b4%a0%e6%95%b0%e5%88%a4%e5%ae%9a%e6%b3%95.
(2) 安全素数 - Wikipedia. https://ja.wikipedia.org/wiki/%E5%AE%89%E5%85%A8%E7%B4%A0%E6%95%B0.
(3) フェルマー数 - Wikipedia. https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A7%E3%83%AB%E3%83%9E%E3%83%BC%E6%95%B0.
(4) 素数とその探求 - 南山大学 理工学部・理工学研究科・理工学 .... http://www.st.nanzan-u.ac.jp/info/gr-thesis/ms/2003/miyamoto/00mm025.pdf.
(5) 素数判定の試し割り法 エラトステネスの篩とは | 趣味の大学数学. https://math-fun.net/20210219/11020/.
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.026s