◆愛知県 Y.M.Ojisan さんからの解答。
【問題１−１】
ｋ として a-2 を用いればよい。
| ∵ (a-2)an+1=(a-1)(an- an-1・・・−１)＝(a-1){1+ | (an-1)*(a-2) a-1 | } |
ｋ として a を用いればよい。
∵ a*an-1=(a-1)(an+ an-1・・・+１)
と因数分解でき、いずれの因数もa≧3なので２以上である。
【問題２−１】
ｋ= 78557 （一例)
【問題２−２】
ｋ=790841 （一例)
∵ 下表は 素数Pを法として ２ｎの周期およびその素因数分解を求め、
素因数が２か３のみのものを求めたものである。
ただし２＜ｐ＜１００００の範囲。
表１ 2n mod P の値
| 素数P | ２ｎ mod P の周期 |
最大素因数 | ２の冪数 | ３の冪数 |
| 3 | 2 | 2 | 1 | 0 |
| 5 | 4 | 2 | 2 | 0 |
| 7 | 3 | 3 | 0 | 1 |
| 13 | 12 | 3 | 2 | 1 |
| 17 | 8 | 2 | 3 | 0 |
| 19 | 18 | 3 | 1 | 2 |
| 37 | 36 | 3 | 2 | 2 |
| 73 | 9 | 3 | 0 | 2 |
| 97 | 48 | 3 | 4 | 1 |
| 109 | 36 | 3 | 2 | 2 |
| 163 | 162 | 3 | 1 | 4 |
| 193 | 96 | 3 | 5 | 1 |
| 241 | 24 | 3 | 3 | 1 |
| 257 | 16 | 2 | 4 | 0 |
| 433 | 72 | 3 | 3 | 2 |
| 487 | 243 | 3 | 0 | 5 |
| 577 | 144 | 3 | 4 | 2 |
| 641 | 64 | 2 | 6 | 0 |
| 673 | 48 | 3 | 4 | 1 |
| 769 | 384 | 3 | 7 | 1 |
| 1153 | 288 | 3 | 5 | 2 |
| 1297 | 648 | 3 | 3 | 4 |
| 1459 | 486 | 3 | 1 | 5 |
| 2593 | 81 | 3 | 0 | 4 |
| 2917 | 972 | 3 | 2 | 5 |
| 3457 | 576 | 3 | 6 | 2 |
| 3889 | 648 | 3 | 3 | 4 |
| 4861 | 972 | 3 | 2 | 5 |
| 6337 | 288 | 3 | 5 | 2 |
| 素数P | 3 | 5 | 7 | 13 |
| ２の冪数 | 1 | 3 | 4 | 2 |
| 1 | 2 | 1 | 1 | 4 |
| 2 | 1 | 2 | 2 | 8 |
| 3 | 2 | 4 | 4 | 3 |
| 4 | 1 | 3 | 1 | 6 |
| 5 | 2 | 1 | 2 | 12 |
| 6 | 1 | 2 | 4 | 11 |
| 7 | 2 | 4 | 1 | 9 |
| 8 | 1 | 3 | 2 | 5 |
| 9 | 2 | 1 | 4 | 10 |
| 10 | 1 | 2 | 1 | 7 |
| 11 | 2 | 4 | 2 | 1 |
| 12 | 1 | 3 | 4 | 2 |
| 素数P | 3 | 5 | 7 | 13 | 19 | 37 | 73 |
| ２の冪数 | 1 | 3 | 4 | 2 | 8 | 31 | 64 |
| 1 | 2 | 1 | 1 | 4 | 16 | 25 | 55 |
| 2 | 1 | 2 | 2 | 8 | 13 | 13 | 37 |
| 3 | 2 | 4 | 4 | 3 | 7 | 26 | 1 |
| ↓ | |||||||
| 15 | 2 | 4 | 4 | 3 | 1 | 10 | 8 |
| ↓ | |||||||
| 27 | 2 | 4 | 4 | 3 | 11 | 1 | 64 |
| 28 | 1 | 3 | 1 | 6 | 3 | 2 | 55 |
| 29 | 2 | 1 | 2 | 12 | 6 | 4 | 37 |
| 30 | 1 | 2 | 4 | 11 | 12 | 8 | 1 |
| 31 | 2 | 4 | 1 | 9 | 5 | 16 | 2 |
| 32 | 1 | 3 | 2 | 5 | 10 | 32 | 4 |
| 33 | 2 | 1 | 4 | 10 | 1 | 27 | 8 |
| 34 | 1 | 2 | 1 | 7 | 2 | 17 | 16 |
| 35 | 2 | 4 | 2 | 1 | 4 | 34 | 32 |
| 36 | 1 | 3 | 4 | 2 | 8 | 31 | 64 |
| 問題2-1 | 2191531 | 7696009 | 19436611 | 34629797 | 13085029 | 10391933 | 78557 | 2191531 | 7696009 | 19436611 |
| 問題2-2 | 34985939 | 8482363 | 31177213 | 790841 | 17710319 | 28482703 | 29829251 | 34985939 | 8482363 | 31177213 |
素数 ３，５，７，１３，１７，２４１を用いて周期２４の場合を考える。
この場合の最小のｋを求めるには、ｋ*２ｎ±１が ｎ＝１〜２４に対して、３，５，７，１３，１７，２４１の何れかを因数にもつようなｋを見つければよい。
なお、ｋは高々 ３*５*７*１３*１７*２４１である。
プログラムを用いて探索すると、この場合
【問題２−１】 ｋ=271129
【問題２−２】 ｋ=509203 であってこちらは解答よりさらに小さい。
なお、先の周期３６のほうの組み合わせの最小を求めると
【問題２−１】 ｋ=78557 であって解答に同じ。
【問題２−２】 ｋ=777149 であって解答よりは小さい。
【感想】
今回、周期の素因数を２と３に限りました。
もっといろいろな素数＆周期の組み合わせで無限に作れそうではあるのですが、意外につくれませんでした。
◆愛知県 Y.M.Ojisan さんからの解答。
【問題２】 無限に素数の組み合わせの違う（周期の違う）ものが存在している。
＜まえおき＞
前回の解をよくよく見てみると、結局、周期解で証明可能なシェルピンスキーないしリセール数は、周期をTとすると
２T-1を因数分解しときに現れる素因数から構成すればよいことがわかります。
従って、５の倍数の周期を持つものとしてT=３０を考えてみると
230-1=32*7*11*31*151*331 であって、6種の素数から構成できる可能性があります。
なお、各素数を法とする２の冪の周期は順に 2,3,10,5,15,30です。
これらをどう初期値を変えてずらせてみても、周期３０中２７個しか、それらの素数の倍数±１にすることしかできません。
つまり周期３０での証明可能な解はないといえます。
＜本題＞
３０の２倍である T=60の場合を考えます。
260-1＝32*52*7*11*13*31*41*61*151*331*1321 です。
まえおきで示したように、素数 3,7,11,31,151,331の６つで
周期３０中２７個をこれらの倍数±１にすることができました。
これは周期６０に拡大すると６箇所足りない状態です。
一方、使われていない素数は、5,13,41,61,1321の５種あります。
従って、６箇所中５箇所は確実に塞ぐことが可能です。
実際にはまず、素数５による周期４の系列のみにより、３箇所塞ぐことが可能です。
つまり周期６０のシェルピンスキーないしリセール数が存在します。
つぎに ｘ15＋１ とその因数分解 の関係を利用します。即ち下記です。
ｘ15＋１＝(１＋ｘ)(１−ｘ＋ｘ2)(１−ｘ＋ｘ2−ｘ3＋ｘ4)(１＋ｘ−ｘ3−ｘ4−ｘ5＋ｘ7＋ｘ8)これの式は、実は ｘが３以上の自然数であるとき、４種の異なる素因数に分解されることを示しています。
互除法によります。途中は省略して結果は下表です。
| ＃ | A | B | GCD(A,B) | 最終的に |
|---|---|---|---|---|
| １ | １＋ｘ | １−ｘ＋ｘ2 | ３ | 共通因数３の可能性 ＊１参照 |
| ２ | １＋ｘ | １−ｘ＋ｘ2−ｘ3＋ｘ4 | ５ | 共通因数５の可能性 ＊２参照 |
| ３ | １＋ｘ | １＋ｘ−ｘ3−ｘ4−ｘ5＋ｘ7＋ｘ8 | １ | 互いに素 |
| ４ | １−ｘ＋ｘ2 | １−ｘ＋ｘ2−ｘ3＋ｘ4 | １ | 互いに素 |
| ５ | １−ｘ＋ｘ2 | １＋ｘ−ｘ3−ｘ4−ｘ5＋ｘ7＋ｘ8 | ５ | Aは５の倍数にはならないので互いに素 |
| ６ | １−ｘ＋ｘ2−ｘ3＋ｘ4 | １＋ｘ−ｘ3−ｘ4−ｘ5＋ｘ7＋ｘ8 | ３ | Aは３の倍数にはならないので互いに素 |
＊１） ＃１の場合 ｘ＝２において A=B=3 であって素因数種類が４個から減少しますが、
ｘ≧３では B＞A＞３ でかつGCD＝3であるので３以外の素因数がかならず現れ、４種より増えることはあっても減ることはありません。
＊２） ＃２の場合 ｘ＞５では B＞A＞５ でかつGCD＝５であるので５以外の素因数がかならず現れ、４種より増えることはあっても減ることはありません。
ｘ＝２，３，の場合は１＋ｘが５を因数に持ちません。
ｘ＝４では計算すると B=５＊４１で ５と４１の２種が存在します。
最後に ２60M−１ (M≧１）を考えます。
２60M−１＝（２30M-1)*（（４M）15＋1)です。
４M＞２ ですから
（（４M）15＋1)は少なくとも４種の素数を因数にもちます。
また一般に GCD(x-1,x+1)=2ですから、
奇数である（２60M-1)と（（４M）15＋1)は共約数を持ちません。
つまり、（（４M）15＋1)の素因数は新しい素数です。
まえに示したように、M=1のとき、シェルピンスキーないしリセール数を作ることができたのですが、６つ抜けている穴を全部塞がずに、最大４個残したとします。
すると、２倍した１２０の周期では８個の穴となりますが、
少なくともその内の４つは（（１６）15＋1)の素因数の素数で塞ぐことができ、穴を４個に維持できます。
以上を繰り返してゆくと、実際には追加素数が４個より多くなる場合があり、穴を少なくとも３個に減少させられます。
次の２倍周期では穴は６個となり、その４個を塞げば、次の２倍周期で丁度穴４個になり、全部塞ぐことが可能です。
なお、証明として（（４M）15＋1)がたまに５種以上の素因数をもつことを証明していませんが、全て４種であるとした場合でも、穴を最大３個に制限すれば、必ず収束させられ、無限に組み合わせが存在することはいえます。