この記事はYahoo!ブログで公開していたもの[1]を元に作成されています。

[1]にある記述が些か分かりにくいものとなっているので、用語の解説と記号の簡素化を加えて全体を書き直した。以下に述べるのは素数に関する問題なので、特段の断りがない限り記号の取り得る値および整数とは「正の整数（自然数）」を意味している。なお、乗算は本来 A * B のように表記されるべきだが、アスタリスクはネット上のドキュメントだと小さくて見づらいので、素因数分解の結果表記を除いて A × B のかけ算表記にしている。
素数に関する問題で、以前から永く温めていたものは沢山ある。そのうちで最近再び考察に上がってきたものを掲載しておこうと思う。なお、類似した問題を過去に誰かが考えているはずだが、言及した記事はまだ見たことがない。他の多くの素数に関する問題同様、肯定的にも否定的にも解決されていないと思われる。

この問題に登場する立役者は素数階乗 p# という数と、それを構成する p# = A × B が成り立つ２個の整数である。1 から n 以下のすべての整数を乗じたものを階乗（factorial）といい n! で表すことに倣って、2 から p 以下のすべての素数を乗じたものを素数階乗（primorial）と表現し、一般に p# と表記される。

素数階乗は、素数が無限個存在することや隣り合った素数の差が無限に大きくなることができる事実を単純明快に証明する過程で援用される。ここではそれらの解説は割愛するが、今から考察する問題は本質的に素数階乗の同様の性質に基づいている。
任意の整数 A と B が 1 以外の公約数を持たないとき、A と B は互いに素であるという。この事実は最大公約数に関する記号を用いて gcd(A,B) = 1 とも書かれる。すべての隣り合った整数は互いに素であるし、３つの連続した奇数はどの２数を取っても互いに素である。
この A-B は A+B に置き換えても成り立つ。A-B に限定しているのは、これから考察する問題に近付けるための下準備である。以下の補題は、この結果と先に考察した p# との橋渡し役となる
記号で書くと分かりづらいが、これは p# = A × B を満たすどのような２つの整数 A,B に分解しても A-B の値が p 以下の公約数を持たないことを意味する。具体的な数値事例として 7# = 2･3･5･7 = 210 から A×B = 210 を満たす A と B を適当に選んでみよう。どのような選び方をしても A-B という値は7よりも大きな素因数しか現れないことが確認される。

これに並行して、ある未知の数値が素数かどうかを調べるもっとも素朴な試し割りに関する判定法を補題化する。
gcd(N,2)≠1 なら gcd(N,4)≠1 なので、試し割りする候補は素数に限定して構わない。上限が√N で足りる根拠は、小さい素数の順に試し割りしたとき√N より大きな素数で割り切れるなら、商となる数はより小さな素数で割り切れている筈だからだ。したがって √N を超えない素数まで試し割りし、割り切れるものが一つもなければ N は実際に素数であると判定できる。

例えば 7# + 1 = 211 が素数がどうかを調べるには√211 ≒ 14.5258…だから13までを試して割り切れなければ素数と確定する。しかし 7# は7以下の素数の積なので 7# + 1 は7以下の素因数を持ち得ず、11 と 13 で割り切れないことを確認するだけで素数と判定できる。素数階乗という積の形を利用して、試し割りの労力を大幅に削減して素数を見つけることができる。そして本題となる以下の問題は、今までの補題を利用して可能な限り効率化することを狙ったものである。
補題１では A-B という差の形に限定した。これは A × B という分解から派生する数値をできるだけ小さくするためである。補題３によれば、整数 N を確定するためには√N までの割り算が必要なので、できるだけ N が小さい方が試し割り候補となる素数の上限が下がる。

ここまでの補題から以下の定理が導かれる。
言葉で表現するなら p# = A × B を満たす２つの数 A,B がなるべく近接している大きさのものを選べば N = A - B を小さくできる。そのサイズを 1< N < p²に押し込めることができれば、試し割りなしに N が素数となることが確定する。

記号の表現上、上限をp² としただけで、実際にはこの上限はもう少し引き上げることができる。特に p が奇素数であればN < p²の上限表記をN ≦ (p+2)²まで改善できる。
（等号が成り立つ場合が存在するかどうかまだ調べていない）

具体的な数値で検討しよう。11# = 2･3･5･7･11 に対して A = 2･3･11, B = 5･7 と選ぶ。N = 66 - 35 = 31 であり、これは 11²よりも小さいので試し割り無しに 31 が素数と確定する。13# = 2･3･5･7･11･13 に対して A = 2･11･13, B = 3･5･7 と選ぶと N = 286 - 105 = 181 である。13²<181<14² だから上限を上回っているものの 13 と 14 の間に素数は一つもないから、やはり 181 が素数と確定するのである。

さて、一連の考察で何を狙っているのか分かるだろう。大きな p# に対して常に定理１を満たすような N = A - B を選ぶ簡単な手段が存在するなら、p から先の p²までの試し割りを全部すっ飛ばして素数と確定できるわけだ。そのためには次の問題が肯定的に解決できるかが鍵となる。
残念ながら、この問題については「そのような方法は存在しない」になるのではないかと予想している。実際にやってみると分かるように、p# がそれほど大きくないうちは事態は極めて良好に進行する。N = 1 となる場合ですら比較的簡単な計算で A,B の分割を見つけられる。
しかしこれらは極めて特殊な事例で、これより大きな p# に対して N = 1 となる A,B の分割は恐らく知られていない。それどころか N < p² を満たす分割さえも探索が非常に困難である。この本質的な原因は、 p が大きくなれば A,B の分割方法が確かに増えるものの、p# の増大速度がそれよりも遙かに大きくて追いつけないからである。
2 は唯一の偶数の素数であり、いくつかの奇素数の積を２つ作って差を取れば常に２で割り切れる。これを利用して問題１に対していくらかでも N を小さくするように焼き直すことができる。
k≧1 であり、A,B の選び方によっては k を更に大きく取ることができる場合がある。途中を省略して 17# に対して A = 3･5･7･17, B = 11･13･19 を選べば A-B = 2²･233 であり、233<19² であるから以後の計算なしに 233 が素数であると確定する。ただし問題１と比較して A,B の組み合わせ個数に変化はないし、N を小さくできる代わりに 2 で何度整除されるか計算する手間が要るトレードオフとなる。

次に23# ともなれば数値自体が急激に大きくなり、A,B が近接したサイズで 23#/2 = A × B を満たす分割を探すのも困難である。すべての分割に対して N は 23 より大きな素因数しか持ち得ないというだけで、計算なしに素数と判定できるのは N < 29² = 529 のサイズまで小さくできた場合に限られる。既知の素数を元に、それらの積と差を計算するだけで遙かに大きな素数を手軽に得ようとする虫の良い目論見も明らかに形勢不利になってきた。

ざっとここまで手計算してみただけでも、先行きは悲観的である。即ち定理１を満たす A,B を選ぶ簡単な方法がないどころか、そのような A,B 自体が有限個しか存在しないのではと思う。p# を定めたとき、問題１あるいは問題２における N の下限を p の関数で評価できるかも知れない。

いずれにしても「p# という形を利用して面倒な試し割りを回避して楽に素数を得る」ことは不可能か、可能であっても結局は試し割り以上に手間が掛かってしまう結果に終わりそうである。そこで p# の形を使うことを諦める代わりに素数を見つける当初の目的は損なわない以下のような拡張を試みた。
素数ベキに置き換えた場合、指数は無限に大きくできる。初めに適当な A,B の振り分けを行い、その後双方の比率を元にして、N ができるだけ小さくなるように個別の素数の指数を調整することができる。19# を拡張する形で極めてナイーヴなアルゴリズムを考えてみた。
実際には (2) の段階でできるだけ比の値が１に近い分割にしておく必要がある。さもなければ以降の過程ですぐに数値が膨れあがってしまい差を一定の水準に押し留めることが困難になる。

この方法まで拡張すれば、差の値が p² より小さくなる分割を見つけることは一応可能である。19# において A = 7･13･17･19, B = 2･3･5･11 とすると、A/B = 89.06…である。これに近い 90 は 2･3²･5 で B の持つ素因数の累乗化のみで対応できるので、C = 90 × B = 2²･3³･5²･11 とすれば C - A = 307 < 19² なので、307 が試し割りなしに素数であることが確定する。

しかし p が更に大きくなれば試し割りなしに得られる素数の水準よりも遙かに大きな数値を扱わなければならない事態は避けられない。この場合も結局は条件を満たすような N を生成する分割は見つかるものの、簡単な数式や手続きからそれを求めることが出来ず、結局は小さい素因数から順に割って行く手段と変わらないか、あるいはそれ以上の手間がかかってしまうことになるという結末になるだろう。

何か別の方向へ拡張したり一般化されれば話は別としても、煩雑な試し割りを回避して大きな素数を求めるという当初の目的はもちろん、何かの応用が効くわけでもなく、結局単なる数字遊びの一つに終わってしまうだろう。
p# という一定の素数より小さいすべての素因数を網羅した数値から派生する問題の一つに、フォーチュン数が知られる。実質的にこれとほぼ等価な命題として、次の予想が存在する。
言葉で表現すれば、p# の前後にある素数までの距離の整数値が常に１か素数になるだろうという主張である。この距離に相当する数がフォーチュン数であるが、今のところどれも１か素数値しか知られていない。「〜は常に素数である」という予想は大抵が反例の発見によって潰えてしまうのだが、この予想は（未だ証明はされていないものの）正しいのではないかと考えられている。

p# から前後にある p# ± p までの数は、p = 1 を除いて常に p 以下の素因数を持つので、直前直後の素数 p# - α, p# + β において α や β が合成数になるためには、その値は p²よりも大きくなければならない。そして p# というオーダーの数が存在する周辺の平均的な素数間の隔たりが α や β よりもずっと小さいのが理由である。

p# - α, p# + β が素数でありながら α, β が合成数となる反例が見つかるケースがあるなら、p# に対応するフォーチュン数を確定させるために α, β を伸張させる過程で合成数 α,β > p² まで到達できたが、その間に合成数を示すシグナルを返さず確率的素数が疑われながらあまりに大き過ぎて判定不可能な数が若干残ってしまうという事態が想像される。予想が正しいなら α, β の上限を抑え込むある関数 f(p) が存在して常に f(p) < p² が成り立つことが証明されて肯定的解決するというパターンになるだろうか。

常に素数であることを主張するステートメントは少ない。フォーチュン数が常に１か素数であることを検証するには、それよりも遙かに大きな素数値が分かっていなければならず、したがって少ない労力で大きな素数を手軽に発掘する方法としてはまるで役に立たない。この状況はウィルソンの定理が極めてシンプルな主張ながら、新たな素数を創り出すにはまるで役に立たないのと同じである。

ある特殊な数式から導かれた数値が、その数式の表現形を利用して小さい素数順に試し割りするよりも労力を大幅に削減できる事例が多く知られている。少なくとも同程度の桁数を持つ数値の完全な素因数分解を得るよりも素数を得る方がはるかに容易なのだが、それにしても桁数が増大すると人類既知のどんな手段をもってしてもまったく手に負えなくなる。好きなだけ大きな数値を手に入れることは数を覚えた幼児にもできることながら、好きなだけ大きな素数を手に入れることに関して、神はその手法を永遠に与えないだろう。

ホームに戻る