English version is here
47*2^n+1 Search
2007/06/03 更新 (2004/07/21 開設)

当プロジェクトは2007年3月をもって終了いたしました。 今までのご協力ありがとうございました。

後続の方の一助となればと、ページは資料としてそのまま残してあります。
当プロジェクトの参加方法の解説: 「47*2^n+1 Searchに参加するには」 (Matさん、ありがとうございます)

現在の進行状況(詳細ページは英語)

表内の数字は n(指数)の値です。
K は x1000, M は x100万 を意味します。

形式 \ 状態探索完了予約済み予約可能準備中
5*2n+1
-2700K
2710K-2712K
-2720K -2740K -3600K
3*2n+1
(n : 奇数)

(配布中断)
(-5100K) (-6600K) --- (-20M)
47*2n+1
(配布中断)
-1830K
(-2000K)
(-2000K) --- ---

 このプロジェクトは主にMat さんのページの素数探索連携掲示板で行っています。
 このページでは参加方法や進行状況をお知らせします。

 素数探索初心者の方はまずこちらをご覧ください。


素数が見つかりました!(2005/04/15 登録)
5*21777515+1
(535087桁、521777511+1 ならびに 621777514+1 の約数)
s-yama さん、おめでとうございます!

主な記録

世界ランキング : 19位 (国内ランキング : 1位)、 Proth 素数 : 世界6位
Generalized Fermat Divisors (any base) : 世界3位
Generalized Fermat Divisors (base=6) : 世界3位

当プロジェクト初となる世界TOP20入りです!


管理人:turbo ( turbo_us_p (at) yahoo.co.jp )


プロジェクトについて

概要

 このプロジェクトは k*2n+1 すなわち2の n 乗に k を掛けて1を足した形の素数を共同で探索するプロジェクトです(プロジェクト名は 47*2n+1 の形をした素数を中心に探していたときの名残です)。
  Proth Search Page の Proth primes search において範囲を予約しているので Proth primes search の子プロジェクトとも言えます。
 現在、47*2^n+1 Search プロジェクトは日本語でのみ参加を受け付けています。英語ページもありますが閲覧専用です。

 発起人は turbo ですが、Proth Search Page の予約は nohara さんにお願いしています。 そのため予約者は nohara さん名義になっていますが、あなたが素数を発見した場合はあなたの名前で世界ランキング (The Prime Pages)に登録することは可能です。

なぜ 47 なのか

 k*2n+1 において、k の値によって素数の出現率は異なります。
 極端な例として、k=78557 や k=271129 では素数は存在しないことが証明されています(このような k をシェルピンスキー数といいます)。
 k=47 は素数は確認されているものの n= 583, 1483, 6115 の3つだけで、素数出現率は非常に低い部類に入るでしょう。
 しかし、k=47 をふるいがけ(小さな素数で試し割りをしてみて、割れれば素数候補から取り除く操作。NewPGen.exe で行えます)すると非常に少ない候補数に絞れる特徴があります。turbo の調べた限りでは、k <= 999 の中で最小でした。
 すなわち、k=47 は k を固定して n を増やしていく探索を行うと同じ時間でより大きい n まで到達できます。
 また、この探索結果は Proth primes search にて全世界に共有されるので仮に合成数しか出なくても探索した意義があると考えています。
 加えて、Fermat Divisor という特殊な素数が見つかりうるおまけもあります(k*2n+1 が素数のとき Fermat Divisor でもある確率は 1/k : k=47 ならば2%強)。 万が一この種類の素数が見つかれば、半永久的に記録に残ることになります。
 Fermat Divisor 狙いで k=5, 7, 9 などの他の形式も探索しています。

目標と注意点

 

  • 目標:現時点では、k=5 において n=3600000 まで準備していますが、それ以上を探索する可能性もあります。


    素数探索に使うソフト

     素数探索初心者の方は以下のページをご覧ください。
    素数探索の基本、ソフトのダウンロード、ソフトの使用について詳しい解説があります。  「第二段階:計算候補をふるい落として高速化」にて NewPGen.exe および PRP.exe が紹介されています。
     PRP3 や LLR も使い方は同じです。

     このプロジェクトでは普段は PRP(Probable Prime:概素数)テストが中心になります (場合によっては希望者に NewPGen によるふるいがけのお手伝いを募集するかもしれません)。
     ここでは比較的ユーザーが多く、登録が不要で無料のソフトを紹介します。
     圧縮してあるので解凍してご利用ください。

    ソフト名 Windows 版 Linux 版 説明
    PRP2414 zip (690K) tar.gz (756K) 最新版。ほとんどの CPU に対応。

     他のバージョンはこちらからダウンロードできます。
     ちなみに、他の素数判定ソフトを使っていただいてもかまいません (上記で紹介したソフトおよび PFGW、Proth は当方で確認していますが、 それ以外のソフトを使う場合は念のためお問い合わせください)。

    知っておくと便利なこと(主にWindows)


    参加手続き

     予約と結果報告の際は Mat さんのページの素数探索連携掲示板を使います(最新の予約状況も確認できます)。
     また、プロジェクトページの進行状況にて募集範囲を確認しておくこともおすすめします。
     注意:このプロジェクトはソフトをインストールすれば自動的に処理が始まるタイプのものではありません。各参加者が手動で設定を行ってください。

    初めて参加する方へ(概要説明)

     Mat さんのページの素数探索連携掲示板 に 7*2^n+1 等のスレッドがあるはずです。通常、各スレッドは一番上の記事にてある区間の募集を宣言し、 その範囲の候補のファイルを添付しています。その下に参加者が予約や結果のレスをつけていきます。
     まだ誰も予約していない範囲が残っているスレッドの中から自分の探したい範囲を選び、 該当するスレッドにレスをつけます(どう書くかは後で述べます)。
     予約した範囲の候補をダウンロードし、ファイル内容を整形したあと PRP.exe または PRP3.exe にて処理させます。
     処理が終了したら予約したスレッドに結果ファイルを添付したレスをつけます。
     基本はこれの繰り返しです。

    <04/09/23 以降に参加された方へ>(それ以前からの参加者では任意とします)
     最初に、管理者の turbo ( turbo_us_p (at) yahoo.co.jp )まで初参加の旨のメールを送ってください。内容は、名前(ハンドルネーム)と連絡先(メールアドレス)だけの事務的なもので十分です。 申告されたメールアドレスは素数発見時の本人確認やプロジェクトに関する連絡に使われ、それ以外には使われません。管理人に連絡したいことがあったらできるだけこのメールアドレスでの連絡をお願いします。

    (追記 2006.08.08)なお、参加メールを送っていただいた時点から候補の予約・解析は可能です。管理人からの許可を待つ必要はありません。 何らかの原因でメールが届いていない場合は再度送信をお願いすることがあります。(PLEさん、ご指摘ありがとうございました)。

    探索範囲を予約する

     初参加の場合は名前を名乗り(ハンドルネーム可)、初参加であることを書いてください。 (一度書けば、他のスレッドや他の k にて初参加の旨を書く必要はありません)。
     同時に探索範囲を「n=430000-440000 を予約します」というふうに宣言してください。

       「初参加の turbo です。n=430000-440000 を予約します。」

     できるだけ他の予約済みの区間と連続して予約してください(飛び飛びの予約は混乱のもとになりますので)。
     予約できる範囲は最小で n 値で100(数個程度に相当)、それ以上は 100 刻みとし、最大で 20000 までとしておきます。 複数のマシンで探索する場合は 20000 以下の区間ずつに区切って予約してください。
     多くとも2ヶ月以内に終えられる量を予約してください。3ヶ月経っても何も連絡がない場合は放棄とみなすことがあります。 こちらには探索時間の見積もりについてのデータがあります。
     既に誰かに予約された範囲や、募集されていない範囲は予約できません。

    予約した範囲の探索をする

     まず、予約した区間の素数候補を素数探索連携掲示板またはプロジェクトページ(このページ)からダウンロードします。
     次に、ダウンロードしたファイルの内容を自分の予約した範囲に合わせて書き換えます。 素数候補のファイルの中身を見ると " 47 400001 " のような数字が並んでいるはずです。 これは 47*2^400001+1 を意味しています。もし n=430000-440000 を予約したのならば 430001-440000 以外の候補は消してください。 なお、1行目に長い数字(ソフトのためのコード)が書かれていると思いますが、それは絶対に消さないで下さい。消すとソフトが動作しなくなります。
    注意:きりの良い数字はそれを上限とする人が探索することにします。例えば n=430000-440000 と書いても、n=430000 は探索せず、実質は n=430001-440000 の範囲を探索します)。
     書き換えたファイルを探索ソフトに入力して探索を始めます(ソフトの使用法はこちらを参照してください)。

    探索完了の通知をする

     探索が終了したら結果ファイルを見て probable prime があったかどうか確かめます。 result.txt ではなく自分で名前を設定した結果ファイル(Test → Input Data... 内の Output file (for proth.exe): に書いたファイル名)を見るほうが早いでしょう。 2行目以降に何も書かれていなければ probable prime はなかったことになります。
     probable prime が見つからなかった場合は予約をしたスレッドにて、「n=430000-440000 に素数はありませんでした」というふうにレスをつけてください。 探索完了の通知と同時に、そのスレッドで募集している別の範囲を予約することもできます。
     このとき探索結果のファイル( PRP.exe における result.txt )のうち今回報告分の結果だけを添付(圧縮推奨)してください。 なぜわざわざ「今回報告分」と書いたのかというと、result.txt は消すなど手を加えたりしない限り前回以前の探索分の結果も記録しているからです。
     なお、結果ファイル添付がない場合は完了とみなしません。
     probable prime が見つかった場合は完了の通知は避け、「素数を発見したら」に従ってください。
     結果ファイルの内容については抜き取り検査を行うことがあります。虚偽報告などが確認された場合、 それ以降の素数探索予約をお断りすることもあります。

    その他


    素数を発見したら

     最初から掲示板で通知することは避けてください。とくに probable prime と出た値は絶対に書き込まないでください。
     悪意のある者が掲示板を見て、自分が見つけたかのように登録することを防ぐためです。

     まず、以下の内容をメールで管理人の turbo および nohara さん( turbo_us_p (at) yahoo.co.jp; tnohara7 (at) wanadoo.fr )まで教えてください。

     ご自分でアカウントを作る場合はこちらを参考にしていただければ幸いです (注意:証明コードは作らないで下さい)。

     送られた値はこちらで素数かどうか確認します。probable prime と判定されても素数でない可能性があるからです(マシンやソフトの不具合ではなく、数学的な性質によるものです)。
     Proth.exe などを使った厳密な素数判定テストを行います。これは PRP テストの何倍もの時間を要しますので結果が出るまでしばらくお待ちください。

     結果が判明したら管理人からメールを送ります。
     素数であった場合はこちらで世界ランキングに登録いたします(Proth primes search への報告もこちらで行っておきます)。

     登録完了後、素数発見の旨もあわせて探索完了の書き込みを掲示板に行ってください。
     プロジェクトページでも素数発見について公に発表します。


    世界ランキング登録を狙える形式

     このプロジェクトで発見されうる素数の中で The Prime Pages の世界ランキングにランクインする可能性が比較的高い形式を紹介します。
     'the top twenty' は The prime pages の TOP20 ランキングを表しています。

    最大既知素数 (Largest Known Primes)

     人類が知っている中で、最も大きい素数のことです。
     素数は無限の大きさまで存在することが分かっているので、 コンピュータが発達する限り記録は伸びていくでしょう。

     参考ページ

    フェルマ数の約数 (Fermat Divisor)

     22m+1(m は正の整数)の形式の数を「フェルマ数」と呼び、 22m+1 のことを Fm と書くこともあります。
     F0〜F4 ではこの数自体が素数となりますが、 F5 以上のフェルマ数で素数のものは見つかっていません。
     フェルマ数 Fm を割る可能性があるのは k*2m+2+1 という形式の素数に限られています。 このような素数は 1/k の確率でフェルマ数の約数となる経験則が知られています。 すなわち我々のプロジェクトのように小さい k で探索すると、発見した素数がフェルマ数の約数である可能性は高くなります。
     フェルマ数は m が大きくなると急激に大きくなるので、フェルマ数を割る素数は非常に貴重です。 2005年6月末時点で 256 個しか発見されていません。
     フェルマ数の約数ほど貴重ではありませんが、「一般フェルマ素数の約数」(Generalized Fermat Divisors) という種類の素数もあります。 これは b2m+1(b, m は自然数)の形式の数を割る素数のことです。 全ての素数はこれにあてはまるため、 The Prime Pages(以下のリンク参照)では b=3,5,6,10,12 の場合のみ特殊な素数として収集されています。

     参考ページ

    Proth 素数

     k*2n+1 の数のうち k < 2n と書ける素数です。  "Proth" は、このような数の高速な素数判定法を発見した人の名前です。

     参考ページ


    Q & A 集

    Q. PRPからもっと多くの候補をインプットするようメッセージが出ました。 PRPがPC起動後の数十秒だけ緑色の表示になってそのあと IDLE状態になったきりうんともすんとも言いません。

    A. PCではテキストファイル(拡張子が.txt)のファイル名はどのように表示されるでしょうか。 WinXPなどではデフォルト設定では、テキストファイルでは拡張子は表示されません。 つまり、PCを使い始めてから何もいじっていない状態だと、 テキストファイル名の.txtの部分が表示されないことになります。 この状態で、例えばデスクトップやエクスプローラーなどで input.txtと表示されるファイルの本当のファイル名はinput.txt.txtです。

    まずはPRP.exeでのinput file名の後に.txtを更に追加してみてください。

    なお、テキストファイル(に限らずどのタイプのファイルでも)拡張子を表示させるようにするにはWinXPの場合で スタート → プログラム → アクセサリ → エクスプローラー(クリック) エクスプローラーを起動させてウィンドウ上部にツールというところがありますが、 ここをクリックすると、フォルダオプションというところが出てきます。 ここで「ファイルの種類」をクリックすると、 しばらく検索した後に現在登録されているファイルの全種類が表示されます。 テキストファイルは結構後ろのほうなので、ずっとスクロールさせると、

    TXT テキストドキュメント

    という項目が見つかると思います。これを選択します。 すると、拡張子TXTの詳細と出てきます。 ここで詳細設定をクリックし、常に拡張子を表示するのボックスにチェックを入れてOKとしてください。 こうすることで、テキストファイルは常に拡張子を表示されている状態になります。 他のタイプのファイルでも拡張子表示が省略されているものは、 同様の操作で表示されるようになります。


    Q. 計算エラーが頻発します。

    A. PC内に埃が溜まっていないかチェックしてみてください。 溜まっているようなら、掃除をすることをお勧めします。 CPUに大きな負荷が長時間連続して掛かるため、発熱が結構馬鹿になりません。


    Q. resultsファイルは消去したほうが何度も探索したときに混乱がなくて良いと判断したんですが、スレッドの範囲が終わるまでは保存していた方が良いでしょうか?

    A. 一応こちらの掲示板にupした段階で消去して構いません。 参加者各自の裁量に任せて、back upを別ファイル名で残したり、自由です。


    管理人:turbo ( turbo_us_p (at) yahoo.co.jp )


    turbo のページTOP