それぞれ4つの異なる素因数を持つ連続する4つの数を求めよという問題です。
ｎの素因数の数を計算し、4つだったらフラグを立てるそれが4回続いたら、おしまいというプログラムで計算できます。
上限がわかっているのなら、素数リストを作ったうえで、素因数の数のリストを求めるというやり方をすれば、計算時間も短く澄みます。例えば1億まで0を並べたリストを作り、2の倍数に1を加える、3の倍数に1を加える・・・と続けていけば素因数の数のリストが出来上がります。
4つなら、この方法が使えるのですが、
「それぞれ５つの異なる素因数を持つ連続する５つの数を求めよ」という問題にすると、1億までには見つかりませんでした。
1億を超えると、メモリが気になります。
そこで時間がかかることは承知の上で、最初に示した方法で計算してみます。
そうすると129963314が見つかりました。
129963314=2×13×37×53×2549
129963315=3×5×31×269×1039
129963316=2^2×7×97×109×439
129963317=11^2×17×23×41×67
129963318=2×3×89×199×1223
でした。
1億越えか・・・
ーーーーーーーーーーーーーーーーーーーーーーー
もっと速くする方法がないのか考えてみました。
4つの連続する数字なので、２つが偶数、2つは奇数です。そして4の倍数が必ず1個あります。
4の倍数が必ず存在するということは、4の倍数をベースに考えればよいということですね。
そこで、数列を4パターンに分けてみます。
① 4n-3, 4n-2,4n-1,4n
② 4n-2,4n-1,4n,4n+1
③ 4n-1,4n,4n+1,4n+2
④ 4n,4n+1,4n+2,4n+3
の4通りです。
この時nが奇数なら素因数の数は3、偶数なら4です。これ以外は不成立になります。
次に、2n-1の素因数の数が4にならなければ、①②は不成立です。
2n+1の素因数の数が4にならなければ③④は不成立です。
この状態で、残りの2つを調べれば調べる数そのものが格段に減ります。実際にやってみると3倍速以上にはなりそうです。
ーーーーーーーーーーーーーーーーーーーーーーー
「それぞれ4つの異なる素因数を持つ連続する6つの数を求めよ」ということで、やってみると見つかりました。
1217250 ＝ 2 × 3^2 × 5^3 × 541
1217251 = 7 × 17 × 53 × 193
1217252 = 2^2 × 23 × 101 × 131
1217253 = 3 × 47 × 89 × 97
1217254= 2 × 19 × 103 × 311
1217255= 5 × 13 × 61 × 307
この時7つ目1217256も4つの異なる素因数を持っていることがわかりました。
このあたりが限界か・・・
1710712055という数字が見つかりました。
ここから、5つの異なる素因数を持つ数字が6つ連続します。めちゃめちゃ時間がかかるので、このあたりがほんとに限界です。