エイプリルフール記事君にこの問題が解けるか!? - INTEGERSで出題した問3の解説を行います。
問題は次のようなものでした:
このとき、任意の自然数
これはGöbel数列と呼ばれている数列で普通は,
で定義されるため、以降を用いて解説します。
最初のいくつかの値を見てみると少し大きめの数が現れることが分かります:
しかし、確かに整数になっています。この問題のどこらへんがエイプリルフールかというと、までは整数であるけれども、実は
が整数ではないのです。
つまり、成り立たないものを証明せよと言っているので、どれだけ証明しようと努力しても証明できません。
更に質の悪いことに、数がとても大きくなっていくのでプログラムを組んで数列の値を実際に出力して整数でないことを示そうと思ってもそうそう簡単ではありません。
天下りではありますが、合同式を使って証明するのがよいです:
証明. のとき、
と計算できる。 Q.E.D.
証明. 補題を使って逐次的に計算を行う:
そうして
であることからがわかる。 Q.E.D.
-Göbel数列
-Göbel数列
は
および
によって定義されます。このとき、
と最初の方の値は整数になっていますが、に至って整数でない値をとります。
-Göbel数列
を
以上の整数とするとき、同様に
-Göbel数列
を
および
によって定義することができます。このとき、新しい数列を
-Göbel数列が初めて整数でない値をとるときの数列の番号によって定義します*1。
です。
補題と同様にしてを証明することができるので、これを用いて
なる最小の
を見つければ一応
を計算することはできます。
のいくつかの値をみると
と、ところで素数ばっかり出てくるのは流石に偶然ですよね?(震え声)
以外の合成数は半素数になっています。
*1:well-definedかどうかは知りません。