テストスレ [無断転載禁止]©2ch.net (762ﾚｽ)
テストスレ [無断転載禁止]©2ch.net http://rio2016.5ch.net/test/read.cgi/math/1470976249/
上
下
前次
1-
新
通常表示
512ﾊﾞｲﾄ分割
ﾚｽ栞
抽出解除
必死ﾁｪｯｶｰ(本家)
(べ)
自ID
ﾚｽ栞
あぼーん
ﾘﾛｰﾄﾞ規制
です｡10分ほどで解除するので､
他のﾌﾞﾗｳｻﾞ
へ避難してください｡
613: １３２人目の素数さん [sage] 2023/11/12(日) 11:59:19.28 ID:yQVh9yuF 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)の素因数は発見したら新発見なんだろうが誰かやるのか？ http://rio2016.5ch.net/test/read.cgi/math/1470976249/613
615: １３２人目の素数さん [] 2023/11/12(日) 12:45:57.77 ID:yQVh9yuF test http://rio2016.5ch.net/test/read.cgi/math/1470976249/615
616: １３２人目の素数さん [] 2023/11/12(日) 13:06:37.66 ID:yQVh9yuF 早速pythonのsympyでF20の素数判定と素因数抽出プログラムを作って流してみたが、実行時間がかかっている。 http://rio2016.5ch.net/test/read.cgi/math/1470976249/616
618: １３２人目の素数さん [] 2023/11/12(日) 14:55:44.23 ID:yQVh9yuF 以下の素数判定プログラムを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つ目の処理を止める。 http://rio2016.5ch.net/test/read.cgi/math/1470976249/618
619: １３２人目の素数さん [] 2023/11/12(日) 15:26:33.48 ID:yQVh9yuF ``` 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日かかるのであきらめる。 http://rio2016.5ch.net/test/read.cgi/math/1470976249/619
620: １３２人目の素数さん [] 2023/11/12(日) 15:56:38.89 ID:yQVh9yuF ローカルにsympyを入れて実行したところcolabより8～64倍速く実行できた。 しかし4096で1分以上かかるので、65536では21～24時間程度かかることになる。 どうせfalseで合成数だろうし、素数ではなく合成数だと分かったところで素因数が分からないと意味がない。 もっと工夫しないといけない。 http://rio2016.5ch.net/test/read.cgi/math/1470976249/620
621: １３２人目の素数さん [] 2023/11/12(日) 16:23:17.54 ID:yQVh9yuF 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 http://rio2016.5ch.net/test/read.cgi/math/1470976249/621
622: １３２人目の素数さん [] 2023/11/12(日) 17:00:44.59 ID:yQVh9yuF 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)まで。 http://rio2016.5ch.net/test/read.cgi/math/1470976249/622
624: １３２人目の素数さん [] 2023/11/12(日) 22:09:09.47 ID:yQVh9yuF ペピンの素数判定法による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 偽 http://rio2016.5ch.net/test/read.cgi/math/1470976249/624
625: １３２人目の素数さん [] 2023/11/12(日) 22:12:06.72 ID:yQVh9yuF ペピンの素数判定法による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 偽 http://rio2016.5ch.net/test/read.cgi/math/1470976249/625
626: １３２人目の素数さん [] 2023/11/12(日) 22:13:58.84 ID:yQVh9yuF F(5)以降のフェルマー数は全部合成数なんじゃね？ つまりフェルマー素数は5個しか無いんじゃね？ http://rio2016.5ch.net/test/read.cgi/math/1470976249/626
627: １３２人目の素数さん [] 2023/11/12(日) 22:16:14.39 ID:yQVh9yuF ペピンの素数判定法とは？ ペピンの素数判定法は、フェルマー数が素数であるかどうかを判定するための方法です³。具体的には、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/. http://rio2016.5ch.net/test/read.cgi/math/1470976249/627
ﾒﾓ帳
(0/65535文字)
上
下
前次
1-
新
書
関
写
板
覧
索
設
栞
歴
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
AAｻﾑﾈｲﾙ
Google検索
Wikipedia
ぬこの手
ぬこTOP
0.034s