素数の原始再帰性の話

アイギスがバグでキメリエスLV16☆４の自分のパターンが終盤で完全崩壊しててわろえない。うーん、これひどいな。

まあそれはともかく。今日散歩してたら、「M.Tani」って書かれたネームプレートのある家を見かけたんですよ。それが目が滑って「Mt.Ani」に見えて、兄山。読み方はニーサンかな？　とか思ってたら、「２３」という数列を思いついて、それでなんとなくこんな話を思いついた。

ユークリッドの有名な素数が無限個あることの証明に次のようなものがあって、背理法で、有限個しかないとして、p_1,...,p_nとしたときに、それらを全部掛け合わせて+1した数が素因数分解できなくなって矛盾、という。

これは面白いことに現代の計算機科学に応用を持ってて、つまり計算可能性を定義するときに使われる原始再帰性って定義があるんだけど、これを素数の集合が満たしていることの証明が上のやり方を使うんだな。原始再帰性を示すためにはnに対して、n+1番目の素数がn番目の素数までを使ったある原始再帰関数の値以下になければいけないんだけど、p_1×...×p_n+1がその役目を果たすねっていうね。

で、面白く思ったので、いろいろ計算してみたんだな。p_1を適当に決めて、ユークリッドのやり方でp_1×...×p_n+1を割り切る最小の素数をp_{n+1}としたらどんな数列が出てくるかなって。たとえばp_1=2なら、

２，３，７，４３，１３，５３，５，……

となる。

面白いのはここからで、p_1=3だと

３，２，７……

と最初の３つが同じなので以降同じ。p_1=7でも、

７，２，３……

となるので以降同じ。で、一桁の素数は７番目に全部揃う。

素数から始めないと約数の素数が出て来ないので、p_1が素数って状況で議論してるとき、一桁の素数で残ってるのはp_1=5。これを計算してみると、

５，２，１１，３，３３１，１９，１９９，……

となって、少なくとも７回目までだと一桁の素数は出て来なさそうだった。

じゃあ７回目が最小なのか？　となると、こんな裏技がある。p_1=17にしよう。すると、

１７，２，５，３，７，……

と、なんと５回目で一桁の素数が全部揃ってしまうのだ。４回で全部揃う可能性は上で全部潰しているから、これが最短である。

……さて。ここで僕がわからない問題がふたつ。

ひとつめ。上の手続きですべての素数が出てくるのだろうか？　一桁の素数は全部出てきたが、p_1=5から始まる列を見ればわかるように、この計算はすぐバーストする。というかp_{n+1}を計算するときにn!以上の数を素因数分解することから始めないといけないのでコンピュータでもすぐ破綻すると思う。だから二桁の素数が全部出てくるかすら検証できてないのだが、果たして全部の素数がこの手続きで出てくるんだろうか？

ふたつめ。１７以外に、上の「５回目で一桁の素数が全部揃う」という性質の素数はあるのか？　案外そのへんにごろんと転がっていたりするんだろうか？　それともこれは１７のみが持つ性質なんだろうか？

以上ふたつの問題、心当たりある人はご一報を。未解決問題だったら面白いな、と思ってたりする。