※ この記事は後書きされています。最終編集日時は 2008/01/30, 12:05 です。
読んでも多くの方には大して面白くもない記事と思うけど、連載モノとして書いておきたいので、人目につかないようにコソコソと sage 進行連載で書いてみることにしようか。
なお、記事は私の手の内にある知識と、ネットで容易に調べられる範囲の情報を元に書いているので、信憑性については保証しませんよ。厳しい追及とツッコミはナシってことで♪
---
数の素数性や含まれる素因数に関する問題や結果として驚愕すべきものは数多くあるが、それらの中で個人的に最も関心を持ったのは Proth Number およびその拡張された形と、そういった数に対する素数性の判定・含まれる素因数についてであった。
Proth Number は、k * 2n + 1 という形で書かれる数で、k = 1 で後ろの符号をマイナスに変えたとき Mersenne Number となるから、その拡張と言うことができる。
Mersenne Number に対しては、早くから効率的な素数判定法（Lucas test）が知られており、現在なお既知最大という栄誉を担っている素数は、この形をしたものとなっている。
Proth Number の興味深い点は k が１より大きな奇数に対しても効率的な素数判定法が存在することと、どんな指数 n に対してもすべてが合成数となってしまうような値 k の存在にある。
この後者の事実に対して、極めて意外に感じたものだった。それと言うのも多項式に含まれる素数性については、あらかじめ式自体に共通因数が含まれているもの、素因数分解されるもの、特定の素因数の法分類によって容易に示されるもの以外は、すべて無限に素数を含むだろうという感触を得ていたからだ。
例えば以下の３つは、どんな整数 n を与えても含まれる素数は有限個数しかない：
f(n) = 3 * ( n + 1 )
g(n) = ( n + 2 ) * ( n + 4 )
h(n) = n2 + 3 * n + 4
これに対して、以下のような式は無限に素数を含むのではないかと予想している。
p(n) = n2 + 1
q(n) = n3 + n + 1
もちろんこれは現在もなお証明されていないものの、ほぼ間違いなく正しいという感触を得ている。
このような状況を見て、指数式に対しても同様の状況になるのではなかろうかと推測していた。つまり
r(n) = 3n - 2
s(n) = 3 * 2n + 1
これらの式はいずれも因数分解されず、しかも特定の素因数を含むことが明らかになってもない。よって一般にこのような形の式には、無限に素数が含まれるだろうという推測をしていたのである。
それだけに、私がその反証となる例を初めて知ったときの驚きは相当なものだった。
78557 * 2n + 1
この式は定数部分が１だから、与えられた k,n に関わらず特定の素因数を持つことは明らかではない。しかしどんな正の数 n に対しても、この式の値が素数となることはない。実際、すべての数は以下のどれかの素因数を必ず含むことが知られている：
3, 5, 7, 13, 19, 37, 73
しかも 78557 に限らず、このような性質を持つ数が無限に存在することが証明されている。そのうちで78557 は最初に知られた実例であり、無限に存在するという証明を提出した数学者の名前に因んで、Sierpinski Number と呼ばれている。
「シェルピンスキー数」
（http://ja.wikipedia.org/wiki/%E3%82%B7%E3%82%A7%E3%83%AB%E3%83%94%E3%83%B3%E3%82%B9%E3%82%AD%E3%83%BC%E6%95%B0）
「Sierpinski Number of the Second Kind」
（http://mathworld.wolfram.com/SierpinskiNumberoftheSecondKind.html）
これらはいずれも「必ず含まれることになってしまう素因数群」（ covering set と呼ばれる）を持つ。covering set に現れる素因数は k によって異なるものの、概ね小さな素因数であることが多い。これはすぐ後で述べる問題を考察するにあたって、一つの重要な鍵を与えているようにも思える。
78557 は定義により Sierpinski Number であるが、それが最小のものかどうかはまだ分かっていない。それと言うのも、定義によれば「どんな n に対しても必ず合成数となってしまう」k であり、これより小さなすべての k に対して反例が見つかる可能性があるからだ。
つまり、78557 よりも小さい k で、値 n を大きくしていっても素数であるものが見つからないものがいくつか残っている。これらが Sierpinski Number ではないことを立証するためには、ある k について素数を示す n を一つでも見つければよい。そうなれば 78557 は最小の Sierpinski Number であることが確定する。
この作業に分散コンピューティングの手法を用い、アイドル状態にあるコンピュータの助けを借りて未確定の k をリストから潰し、最終的に 78557 が最小の Sierpinski Number であることを証明する Seventeen or Bust プロジェクトがある。
「Seventeen or Bust」
（http://www.seventeenorbust.com/）
「Proth Number およびその拡張された形の数について【２】」に続く