掲示板分散やccの話題他、ご自由にどうぞ

掲示板分散やccの話題他、ご自由にどうぞ

47*2^n+1　投稿者：turbo 投稿日：2004/07/16(Fri) 14:10 No.133

Nohara さん wrote:
k*2^n+1の場合なら、例えばk=45とk=47とでその違いを
ぜひ比べてください。

比べてみました。
n=1M までで、p=10M までふるった後の残り候補数です。
k=45 : 100591
k=47 : 7523
もっと極端な例もあります。
k=20010705 : 196582
k=271129 : 0 (p=239で終了。シェルピンスキー数です)

k=20010705 は日付素数探索の際に発見したものです。
n=10000 までで（たしか）51 個もの素数を持ちます。
多くの k では10個程度だと思います。k=47 は３つだけです。
一時は k=20010705 で TOP5000 を目指していましたが、
マシンのスペックが低かったので探索範囲を5000位に抜かれてしまいました（笑）。

Seventeen Or Bust が k=5359 のとき n=5054502 で初めて素数となることを発見していますが、
上記と同じようにふるいをかけてみると、
k=5359 : 8276
他には n=698207 が最小の素数である
k=46157 : 3839
などがあり、候補数が少ないからといって素数が見つからないわけではないですね。
単純に考えると 47*2^n+1 で次の素数（最大既知は n=6115?）は n=1000000 くらいでしょうか？
現在 47*2^n+1 を探索しようかどうか考え中ですが、１人では徒労に終わりそうな気もします。

Re: 47*2^n+1　nohara - 2004/07/16(Fri) 21:06 No.134

turboさん、情報ありがとうございます。

k*2^n+1/-1についての話は、森井研究室の素数探索プロジェクト内
での私の書き込みSierpinski問題、Riesel問題ならびにBrier数
のところで説明しました。
　これらは素数が永久に出現しない例です。

turboさんの20010705を素因数分解すると、
20010705 = 3 * 5 * 11 * 13 * 19 * 491
となります。つまり、20010705*2^n+1という数列を考えると、
これらは絶対に3,5,11,13,19および491では割り切れない
ことが分かります。2^n*3*5*11*13*19*491+1は上記の素数で
割れば、nに関係なく1余るのは明らかです。
このようにkを多くの異なる素因数で構成すれば、素数出現
頻度が高いkを得やすくなります。もちろん、そうとは限らない
ことも言うまでもありません。

k=75075=3 * 5^2 * 7 * 11 * 13

の場合も75075*2^n+1の素数出現頻度は同様に高くなります。

このようなkの値については

http://www.primepuzzles.net/puzzles/puzz_006.htm

に解説があります。
10000までに80個以上の素数が出現する例があります。

ちなみにk=47で素数探索を考えている場合、私もよかったら
参加しますよ。p=1e7まで篩を実施して100万までで7500個
しか候補に残らないのであれば、残り候補4000個強まで
ふるいを実施できそうですね。n=40万くらいまではすでに
探索済みのはずです。となると...100万まで行っても見つ
からない可能性の方が高そうですね。

なお、proth prime searchで予約を取りたい場合、
パスワードを要求されますが、参加される前にRay Ballinger
氏に、参加したいから教えて頂戴とメールを送付すれば、
ユーザー名とパスワードを教えてくれます。

　あと、Proth prime searchに参加しようとする場合
参加者に掛けられている言葉を和訳して紹介します。

　予約した範囲で素数が残念ながら見つからなかった場合でも
その範囲では素数が無かったという報告を是非ともお願いします。
　その情報はあるk*2^n+1という素数が見つかった、ということと
同様に価値があるのです。

Re: 47*2^n+1　nohara - 2004/07/16(Fri) 21:17 No.135

いくつか補足します

turboさんwrote:
>Seventeen Or Bust が k=5359 のとき n=5054502 で初めて素数となることを発見していますが、
>上記と同じようにふるいをかけてみると、

これは最小性については確認されていなかった、と思います。
個人的にはまず間違いなく最小である、と思っていますが。

　話は全然変わるのですが

　また、先の書き込みの最後の紹介の意図は何かというと、
私は分散プロジェクトそのものに勝者を決める、という
考えが全くしっくりきません。
　ここの管理人さんであるMat氏はじめ、分散コンピュー
ティングに興味がある人は勝者にこだわっている
ことが多いように見受けられますが、私はその考えは
賛同しかねます。外れの領域を探索した人がいて、
その領域がチェック済みである、という情報が
あってそれをマネージメントしてこその成果という
当たり前の事実を見失っているのではないでしょうか。
　勝者があるとすれば、そのプロジェクトの立案者
であり、参加者全てでしょう。まあ、発見者（当りを
引いた人）に少しの名誉（と賞金など）が与えられる
のは理解できますが、あまりにもそれを強調するのは
おかしいと思っています。

Re: 47*2^n+1　higa - 2004/07/17(Sat) 04:20 No.136

初めましてhigaと申します。
Matさんの"わたしの素数"を読んだのがきっかけで
今年の3月頃から素数探索にはまっています。

Noharaさんwrote:
>turboさんの20010705を素因数分解すると、
>20010705 = 3 * 5 * 11 * 13 * 19 * 491
>となります。つまり、20010705*2^n+1という数列を考えると、
>これらは絶対に3,5,11,13,19および491では割り切れない
>ことが分かります。2^n*3*5*11*13*19*491+1は上記の素数で
>割れば、nに関係なく1余るのは明らかです。
>このようにkを多くの異なる素因数で構成すれば、素数出現
>頻度が高いkを得やすくなります。もちろん、そうとは限らない
>ことも言うまでもありません。

上記のNoharaさんの話が面白そうだったのでk=265995345で
k*2^n+1の形で探索してみています。
265995345=3*5*7*11*17*19*23*31 と多くの異なる素因数
で構成されていますので，良い結果を期待しています。

ところで当然のことかもしれませんが，多くの異なる素因数を
含む値をkにしたときにk*2^n+1とk*2^n-1の両方の素数出現頻度
が高くということは，探索している候補の中から双子素数が
見つかる確率は通常より高くなると考えていいのでしょうか？
ためしに 265995345*2^n+1 でn=1～1000を試したところ
n=42,73,90が双子素数になりました(日付素数を探してい
るときは双子素数は今まで0個でした)。

もし，双子素数の探索が少しは容易になる形なのなら，
双子素数のTOP20までに入る程度の大きさで探してみても面白い
かなと思いました。
# kを固定するために双子素数の候補数を多く取れないという点
# が少し不安です。

Re: 47*2^n+1　nohara - 2004/07/17(Sat) 06:03 No.137

higaさん　はじめまして

まず、

>265995345=3*5*7*11*17*19*23*31 と多くの異なる素因数
>で構成されていますので，良い結果を期待しています。

十分いいのではないでしょうか。
私もこの方面の知識（実験なども含む）はそれほど無いのですが、
上記のほかに、いくつか素因数を入れ替えてみたり、
小さな素数は2乗させたりすることで、よりよい素数頻度
の数列を探せるかと思います。
　またふるいだけではなく、実際にn=3000程度まで素数を
探させてみて、素数が実際に多く出現することを確かめる
ことも重要かと思います。k値の選定は少し時間を掛けて
行っても良いかもしれません。探索と平行していろいろ
考察するのも、単にコンピュータの計算を待っているより
よいでしょう。

　Prime Pagesで登録されている素数をいろいろ見てみると、
そうやって探したと思われるk値固定で素数探索を行っている
例が散見されます。

しかし、

>ところで当然のことかもしれませんが，多くの異なる素因数を
>含む値をkにしたときにk*2^n+1とk*2^n-1の両方の素数出現頻度
>が高くということは，探索している候補の中から双子素数が
>見つかる確率は通常より高くなると考えていいのでしょうか？

上記の点については、higaさんの言われることは正しいのですが、
実際これを利用して双子素数探索はkをどうやって選んでも不安
どころか、ほぼ絶望的です。双子素数を探される場合は、nを固定
し、kをふるいに掛けるほうがはるかに合理的です。

Top20位以内を目指すとすれば、15000桁程度はターゲットに
探索することになるかと思います。現時点ではそれ以下でも
よいのですが、発見される時期に20位以内となりうるかも
考える必要があるからです。
15000桁の双子素数であれば、10万桁素数を見つけるよりやや
難しい程度ではないかと思います。
　双子素数の出現頻度はおおよそ桁数の2乗に反比例することが
経験的に知られています。これから双子素数探索難易度は桁数の
およそ4乗に比例することがいえます。持っている計算能力
とターゲットとのバランスを考慮することも非常に重要です。
　やや高めのターゲットを選定して、素数探索連携掲示板で
仲間を募集をするというのもよいでしょう。

双子素数を探される場合は
NewPGenのtwinモードでふるいを実施します。
nは固定し、kの範囲は少なくとも5億かできれば10億程度
とります。（15000桁をターゲットとする場合です)
ふるい終了後、残り候補をPRPテスト実施していきます。
判定させる形式はk*2^n+1かk*2^n-1のどちらかに固定
するとよいでしょう。
　全範囲を探索しても素数が見つからなかった場合は
nを変えて同様に探索していきます。

Re: 47*2^n+1　turbo - 2004/07/17(Sat) 17:46 No.142

nohara さん wrote:
> これは最小性については確認されていなかった、と思います。

失礼しました。
GIMPS のように２回チェックしないと確認とは認められないということなのでしょうか？

proth prime search の存在を知らなかったので危うく n=1 から調べるところでした。
教えていただいてありがとうございます。
とりあえず Ray Ballinger 氏に参加表明のメールを送りました。
現在返信待ちです。
できればページの和訳をお願いします。
k=47 の探索も無理のない範囲でご協力お願いします。

nohara さんが補足のレスにて書かれたことを読んで改めて思いましたが、
チェック済みの範囲の情報にはかなり助けられています。
素数探索を始めたころを中心に通算１ヶ月くらいは無知ゆえの無駄な計算をしています。
いや、今もです（前述参照）。他の方による探索済みの範囲のふるいもたくさん行っていました（笑）。

願わくば誰かが「素数・合成数データベース」を作ってサーバを運営し、
すべての素数判定ソフトにそのサーバとの連絡機能が盛り込まれることで自動的に結果がサーバに送信され、
また、ある数を調べようとしたら「その数は既に合成数と判明しています」と表示されたらいいな、と思っています。
そうすれば「第２のふるい」が誕生するわけですが、実現は難しそうですね。

P.S.
k を固定した場合の k*2^n+1/-1 の PRP テストの時間を見積もってみました。

---------------------------------------------------------
まずふるいのことは考えないでおく。
k*2^n+1/-1 を PRP テストで調べるのにかかる時間を An とおく（n が十分大きい時 k は無視できるとする）。
An = c * n^2 （c は n=1 のときにかかる時間）であるだろうから、1 から n 項目までの和 Tn = c * n(n+1)(2n+1) / 6
これは n が大きい時 c * n^3 / 3 とできる。
ここで、nohara さんの「素数発見難度の評価」より
1GHz のマシンが 10万桁の数（n=330000 とする）を１つ PRP テストするのに必要な時間は 1850 秒であることを用いると、
A_330000 = c * 330000^2 = 1850 s
(c ≒ 1.7 * 10^-8 s と分かる)
よって
T_330000 = c * 330000^3 / 3 = (c * 330000^2) * 330000 / 3
　　　　 = 1850 s * 330000 / 3 = 2.035 * 10^8 s ≒ 56500 h ≒ 6.4 y
ただしこれはふるいなしで PRP にかけた場合の話である。
k=47 の場合、0.4% 程度までふるい落とせると仮定すると、PRP テストの時間は
0.004 * 56500 h = 226 h = 9.4 d
まで減らせる。

一般的な式にすると、n まで PRP テストを行うのにかかる時間 Tn は
Tn = 5.67 * 10^-9 * a_k * n^3 / cpu
a_k : ふるいにて減らせる比率（k によって異なる。k=47 では約 0.004）
cpu : マシンのスペック (GHz単位)

さて、Tn は n^3 に比例するので n=100万の場合 n=33万の約 3^3 倍かかる
226 h * 3^3 ≒ 254 d = 8.5 months (1GHz)
-----------------------------------------------------------
n=43万まで探索済みであることを差し引くと７ヶ月強でしょうか。
n=100万くらいまでなら少人数でも行けそうですね。

Re: 47*2^n+1　nohara - 2004/07/17(Sat) 20:43 No.143

>失礼しました。
>GIMPS のように２回チェックしないと確認とは認められないということなのでしょうか？

実は私もはっきりしないまま書いてしまったところがありますが、

Seventeen or Bustのstatusの詳細ページがあります

http://www.seventeenorbust.com/stats/rangeStatsEx.mhtml

ここの項目で、n Bounds upperというのがあります。
これは、これより小さいnについては全部チェックしているよ、
という意味です。
5359のところはn/aとなっていて不明なのですが、ひょっと
したらチェック済みかもしれません。ただ、私はそれを確認する
ことができないので、とりあえず未確認状態と判断しています。

Riesel Sieve projectではRiesel数について同様の探索を行っ
ていますが、こちらの方も、素数が見つかったといっても各k値
における最小性については確認していないそうです。
これはRiesel problemのところで、
http://www.prothsearch.net/rieselprob.html
一番下のほうに、
The largest prime discovered during this investigation is the 420150-digit
prime 192089.2^1395688 - 1 found by Riesel Sieve group.
という紹介があります。かつてはこれに追加して、
例えば、192089.2^n-1 are always composites until n=1395688
というような文章も付加されていましたが、Riesel sieve
projectで発見された例については全てこのような文章はつい
ていません。(他の個人で発見された例には例外なくついていた）
また、今は無くなっているのですが、かつてはこの
プロジェクトで報告されている素数については最小性
は確認していない、ということも書いてありました。

　Seventeen or Bustについても、同様ではないかと
推測している次第です。

Proth Prime Searchの翻訳がんばります。

ついでにここ2,3日、日本人の素数登録が急激に増えましたね。

Re: 47*2^n+1　sk 3141592 - 2004/07/17(Sat) 21:44 No.145

こちらの話題を元に、k*2^n-1の形でkをいろいろ変えてやってみました。
その中で1つ面白そうなのが見つかりました。
k=14549535 =3^2 * 5 * 7 * 11 * 13 * 17 * 19
n=1M,p=10Mまでのふるい落としで残りが269012個。
n=10000までに82個の素数が発見できました。

まだPrimePagesには登録がないようなので、しばらくこの値を調べてみようと思います。

Re: 47*2^n+1　higa - 2004/07/30(Fri) 06:36 No.155

Noharaさんwrote:
>双子素数を探される場合は
>NewPGenのtwinモードでふるいを実施します。
>nは固定し、kの範囲は少なくとも5億かできれば10億程度
>とります。（15000桁をターゲットとする場合です)
>ふるい終了後、残り候補をPRPテスト実施していきます。
>判定させる形式はk*2^n+1かk*2^n-1のどちらかに固定
>するとよいでしょう。
>　全範囲を探索しても素数が見つからなかった場合は
>nを変えて同様に探索していきます。

やってみました．
強運だったのか，kを1から1億ちょっとまで探したところで
双子素数が見つかりました．
168030135*2^51111-1/+1 15395桁(登録済み)

特殊な素数を登録したのは初めてなので嬉しいです．
探索期間はPentium4 2.8Ghzのマシンでおよそ10日間でした．

>　双子素数の出現頻度はおおよそ桁数の2乗に反比例することが
>経験的に知られています。これから双子素数探索難易度は桁数の
>およそ4乗に比例することがいえます。持っている計算能力
>とターゲットとのバランスを考慮することも非常に重要です。

双子素数の新記録を狙うとすると今回発見したものと比べて桁数
が4倍程度になります．
今回のような強運が働いたとしても10日*4^4=2560日は大変
なので，もし探すとしても個人で探すのはやめておきます．

Re: 47*2^n+1　nohara - 2004/07/31(Sat) 06:19 No.156

higaさん

双子素数発見すごいですね。
わずか10日で発見するとは。kのレンジ5-10億というのは、
大体この区間を全体探索すると、15000桁くらいだと双子
素数1個はヒットするという目安でしたが、早めに見つか
りましたね。

>今回のような強運が働いたとしても10日*4^4=2560日は大変
>なので，もし探すとしても個人で探すのはやめておきます．

実は、それでも100万桁素数を見つけるよりはずっと簡単なので、
私としては森井先生が素数探索プロジェクトを再度立ち上げる際、
同じ参加者規模を期待するなら、今までの記録を後追いするのでは
なく、双子素数の世界記録を狙うというのもいいのでは無いか、
と思うことがあります。今更非メルセンヌ素数で100万桁でも
非メルセンヌ素数での世界一になれる訳でもないですし。

ちなみにコードg294やL4の大量登録は双子素数狙いの残渣です。
その他にもトライされている方が居るとは思いますが。
個人でこれらに追いつくのは到底不可能ですが、
団体ならば負けないかも。

Re: 47*2^n+1　216091 - 2004/07/31(Sat) 20:00 No.158

こんにちは、

腕試しに　1085735*2^2171676-1　などを探していた
のですが、正しい？素数探索の方法としては、NewPgen
で双子素数でふるいにかけた後に+1　の方を　PRP(or　LLR)
でチェックし(+1はフェルマー数を割る可能性があるので)
素数だったら　-1　の方も　LLR　にかけるという方法
でしょうか。

P2Pプロジェクトで　GFN素数を探索するのには意味がある
と思います。最大の素数がGFN素数でなくて　Mersenne素数
なのは単に探しているパソコンの数がMersenne素数の方が
多いからだと思うからです。GFNはふるいがMersenne数と
同じ効率で行うことができます。（3*2^n+1　はこの点で不利）
proth.exe　は　prime95　より倍遅いですが、最大の素数を
探索する場合に　Mersenne素数は数が少ないのでより大きな数
を探さなければならないので使う　総CPU時間としてはGFNの方
が少なくて済みそうです。問題があるとすればGFN素数は最大
でなくなってしまえばただの素数になってしまう点でしょうか。

徳島大で作られた　Java　の通信プログラムは申し分のないもの
なので　proth.exe　に欠けていた部分を補ったといえると思います。
（proth.exeより高速な　GFN素数探索プログラムが作れるのはWaltman
だけでしょう）
100万桁を達成したら余勢を駆って1000万桁に挑戦すれば良いと思います。

#s-yamaさんは順調に保有素数を増やしておられますね。

ＰＲＰで素数と判定されない？　投稿者：ayuchan 投稿日：2004/07/29(Thu) 16:31 No.154

ＬＬＲの裏技？の話題から日付素数の判定をＰＲＰとＬＬＲの両方でやったところ、ＰＲＰで素数と判定されないものが、ＬＬＲでは素数と判定されるものがありました。

lrsults.txt（ＬＬＲ）
19950831*2^7+1 is a probable prime. Time : 24.573 ms.
19950831*2^9+1 is a probable prime. Time : 664.133 ms.
19950831*2^24+1 is a probable prime. Time : 952.143 ms.

rsults.txt（ＰＲＰ）
19950831*2^7+1 is not prime. Res64: 000000001A6AD13B
19950831*2^9+1 is not prime. Res64: 00000001E3687CC2
19950831*2^24+1 is a probable prime.

ｐｒｏｔｈでは、19950831 >= 2^24 と出て判定できないので、
ｐｆｇｗで確認したところ全て素数と判定されました。

Re: ＰＲＰで素数と判定されない？　turbo - 2004/07/31(Sat) 16:52 No.157

こちらでも確認できました。

n=24, k=16775000-16780000 をやってみるとよく分かります。
NewPGen で最後（ソフトの右下に Sieve terminated : All remaining values と出る。ここでは p=1680万くらい）まで行うと素数しか残らないはずなのですが、PRP では k < 16777216(=2^24) だと多くが非素数と判定されます。

いろいろやってみたところ、
k*2^24+1 では約900万 < k < 2^24 の結果は信頼できないようです。
また、k*2^24-1 でも PRP は同傾向を示しました。
LLR では k < 2^24 のときは素数であることを確定できるようです。（ k*2^24-1 is prime! と出ます）

LLR の裏技？　投稿者：turbo 投稿日：2004/07/23(Fri) 17:52 No.149

LLR は k*2^n-1 だけを判定するソフトということになっています。
しかし別の形式（例えば k*2^n+1 ）を判定させると
"Warning : LLR tests only k*2^n-1 numbers, so, PRP is used for the other tests."
と文句を言いますが一応やってくれます。

PRP と LLR の k*2^n+1 の処理時間を比較してみたところ面白い結果が出ました。

＜3*2^n+1 を P3 700MHz で判定したときの Time per bit (msec)＞

n=600000
　　PRP 15.11
　　LLR 15.135
n=700000
　　PRP 24.85
　　LLR 23.12 (93.0%)
n=1000000
　　PRP 36.21
　　LLR 33.72 (93.1%)
n=1300000
　　PRP 39.86
　　LLR 36.86 (92.5%)
n=1500000
　　PRP 56.485
　　LLR 56.06

だいたい n=688000-1300000 にて PRP の 93% 程度の時間で判定できるようです。

LLR のソフトの説明によると PRP (ver 2.0.2)を下敷きにしているようなので k*2^n+1 が判定できてもおかしくないですが、最新版のPRP (ver 2.3.0) より早いのには驚きました。

Re: LLR の裏技？　nohara - 2004/07/24(Sat) 06:00 No.150

turboさん、本当ですか。私も実は同じようなことを
トライしたのですが、うまく動作しませんでした。
　バージョンが異なるせいかもしれません。

　計算結果が信頼できるのであれば、トライする価値は
ありますね。

Re: LLR の裏技？　ayuchan - 2004/07/24(Sat) 14:20 No.151

turboさんの日付素数に投稿した素数を使い、同じ条件で調べてみました。

19650919*2^10181-1　[3073桁]
　PRP 105.771sec
　LLR 102.984sec(97.4%)

19650919*2^8426+1　[2544桁]
　PRP 83.217sec
　LLR 81.942sec(98.5%)
念の為２回目
　PRP 84.173sec
　LLR 79.115sec(94.0%)

どちらの場合もＬＬＲの方が早いですし、probable primeと判定されました。

Re: LLR の裏技？　turbo - 2004/07/25(Sun) 12:56 No.152

今度は P4 2.8GHz でやってみました。

9*2^461081+1
　　PRP(ver 2.3.0) 1031.472s
　　LLR(ver 2.0.0)　984.037s (95.4%)
どちらも probable prime と判定されました。

また、3*2^n+1, n=10万-500万での Time per bit の比率( LLR / PRP )をとってみたところ

n=10-30万　96%
n=40,50万　93%
n=60,70万　97%
n=80-400万　98%
n=500万　　99%

マシンや範囲によって差はありますが、LLR が早いのは変わらないようです。

Re: LLR の裏技？　nohara - 2004/07/25(Sun) 22:32 No.153

改めてLLRをダウンロードしなおしたところ、
私のパソコンでも動作しました。
　ただ、AthlonMP2800+上では速度差はほとんどみられていません。

　ところで、P4-2.8M 9*2^461081+1判定に1000秒ほどとは
ずいぶん速いですね。
AthlonMP 2800+(2133M/FSB 266M)では1520秒程度、
AthlonXP 3000+(2166M/FSB 333M)で推定1420秒程度です。

　Woltman氏のFFTはP4系はやはり圧倒的に強いですね。
メルセンヌ数探索におけるベンチマークテスト差も頷けます。

genefer128　投稿者：216091 投稿日：2004/07/17(Sat) 12:37 No.141

こんにちは、

http://netnews.gotdns.org/WallStreet/6351/txt/genefer128.c

genefer.c を改造して (b^2)^n+1 をテストするようにして
計算機をブン回して

$ ./genefer128
GeneFer 1.3 (Alpha 128-bit) Copyright (C) 2001-2002, Yves GALLOT
A program for finding large probable generalized Fermat primes.

(b^2)^(2^n)+1 (b=2,4,6,8,... n=1,2,3,4,...)

Usage: GeneFer -b run bench
GeneFer -t run test
GeneFer <filename> test <filename>
GeneFer use interactive mode

1. bench
2. test
3. normal
3
N: 4096
b: 1799426
3237933929476^4096+1 is a probable prime. (err = 3.12e-01)

を見つけたと思って Prime page に登録に行ったところ

* The description "3237933929476^4096+1" was modified to "1799426^8192+1"
in accordance with our canonicalization procedures.

だそうです。そうですね。

(b^3)^n+1 をテストするようにもできると思うんですが、
これは素数にならないですね。

Re: genefer128　nohara - 2004/07/18(Sun) 08:36 No.146

>(b^3)^n+1 をテストするようにもできると思うんですが、
>これは素数にならないですね。

216091さん、いいところに気が付かれましたね。
これに気が付くと、例えば、b^8192+1等を探索しているときに、
bがある偶数の3乗だったり、5乗だったりすれば、素数判定
するまでも無く、素数候補から除去できるわけです。
　例えば、20123648^8192+1は20123648=272^3なので、
これは素数判定を実施するまでも無く、合成数であることが
分かるのです。

20123648^8192+1
= (272^3)^8192+1
= (272^8192+1) * (272^16384-272^8192+1)

また、bがある偶数の2乗であれば、大抵はその数はすでに
b^16384+1の素数候補として探索済みなので、これらも
除去できる訳です。
20000000以上であれば、
20016676, 20034576, 20052484, 20070400, 20088324,
20106526, 20124196....等がそうになります。

素数登録マニュアル　投稿者：turbo 投稿日：2004/07/10(Sat) 02:32 No.119

簡易版ですがやっと完成しました。
http://www.geocities.jp/turbo_us_p/toukou.html

余裕の出てくる秋以降に改良を加える予定です。

Re: 素数登録マニュアル　nohara - 2004/07/10(Sat) 06:21 No.120

turboさん

早速拝見しました。
すばらしい。これで十分ではないでしょうか。

かつて、私がこのマニュアルを作ろうとして断念したこと
を思い出します。

Re: 素数登録マニュアル　s-yama - 2004/07/11(Sun) 07:22 No.123

turboさん、登録できました。素数も3個登録しました。
rank,scoreがあって、おもしろいですね。
しかし、あまり眺め過ぎると、またPC増設病になりそうです。

Re: 素数登録マニュアル　turbo - 2004/07/11(Sun) 17:38 No.125

登録できて何よりです。
英語の壁だけで参加を断念するのはもったいないですからね。
このマニュアルをきっかけに高校生などの学生の参加も増えれば幸いです。

＃s-yama さんの投稿された素数について、なかなか向こうの証明が終わらないなと思っていたら、世界TOP10クラスの素数（1361244^131072+1）が投稿されてなかなか手が回らないようですね。
The Prime Pages 側の処理状況はここで確認できます。
http://primes.utm.edu/primes/status.php

Re: 素数登録マニュアル　nohara - 2004/07/11(Sun) 18:20 No.126

turboさんwrote:
英語の壁だけで参加を断念するのはもったいないですからね。
このマニュアルをきっかけに高校生などの学生の参加も増えれば幸いです。

私がはじめて参加したときも、登録はこれでいいのだろうかと
かなりどきどきしていました。懐かしい思い出です。
　高校生の参加で思い出したのが、Michael Eatonさんは
15万桁の素数を17才の高校生の時に発見しています。
　昨年だったと思うのですが、新しいProth prime探索の
参加者が来たな、と思ったらその後高校生と知って驚いた
記憶があります。

　また、過去にはTop10クラスの素数でも偽登録（合成数を
素数と登録）が私の知る限りで3回ありました。しかも当時は
チェックは行っていなかったので、Prime Top 10　listに
そのまま掲載されていました。大抵の場合は数日後に合成数
と判明して削除されたのですが、気分の良いものではありません。
　そのような事情があって、Prime Pagesでは登録素数を
チェックするようになりました。

s-yamaさんwrote
しかし、あまり眺め過ぎると、またPC増設病になりそうです。

非常によくわかります。

Re: 素数登録マニュアル　ayuchan - 2004/07/17(Sat) 21:41 No.144

素数登録マニュアルのおかげで、本日Prime Pages に素数を登録することが出来ました。

turboさんありがとうございました。

日付素数探索これからもがんばります。

[直接移動] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21]

- Joyful Note - Edit:Mat