Cマガ電脳クラブ(第047回) 素数列

問題

次のような数列を考える。
　P(n+1) = 2*P(n) - 1
つまり、「2倍して1を引く」ことで続く数列だ。

この漸化式を満たす「連続した8項」の数列があり、それがすべて素数であるという。
そんな数列はいくつもあるが、その中で最小の初項を持つものをみつけてほしい。

ソース

using System;
using System.Collections.Generic;

class Program
{
    const int Jyougen = 16000000; //数列の初項の上限
    static int[] SosuuArr;

    //エラトステネスの篩
    static void Eratosthenes()
    {
        var IsSosuuArr = new System.Collections.BitArray(Jyougen + 1);

        for (int I = 2; I <= IsSosuuArr.Count - 1; I++) {
            IsSosuuArr[I] = true;
        }
        for (int I = 2; I * I <= IsSosuuArr.Count - 1; I++) {
            if (IsSosuuArr[I] == false) continue;
            for (int J = I * 2; J <= IsSosuuArr.Count - 1; J += I) {
                IsSosuuArr[J] = false;
            }
        }
        var SosuuList = new List<int>();
        for (int I = 2; I <= IsSosuuArr.Count - 1; I++) {
            if (IsSosuuArr[I]) SosuuList.Add(I);
        }
        SosuuArr = SosuuList.ToArray();
    }

    static void Main()
    {
        var sw = System.Diagnostics.Stopwatch.StartNew();
        Console.WriteLine("数列の初項の上限を、{0}として検証します", Jyougen);
        Eratosthenes();

        //数列の次の項を求める
        Func<long, long> DeriveNextVal = pCurrVal => 2 * pCurrVal - 1;

        //素数でループ
        for (int P = 0; P <= SosuuArr.GetUpperBound(0); P++) {
            long CurrVal = SosuuArr[P];
            bool IsOK = true;
            var SuuretuList = new List<long>() { CurrVal };

            for (int N = 2; N <= 8; N++) {
                CurrVal = DeriveNextVal(CurrVal);
                SuuretuList.Add(CurrVal);
                if (IsSosuu(CurrVal) == false) {
                    IsOK = false;
                    break;
                }
            }
            if (IsOK) {
                Console.WriteLine("解は{0}で、数列は", SosuuArr[P]);
                SuuretuList.ForEach(X => Console.WriteLine("{0,10}", X));

                Console.WriteLine("経過時間={0}", sw.Elapsed);
                return;
            }
        }
    }

    //奇数が素数かを判定
    static bool IsSosuu(long pTargetOdd)
    {
        if (pTargetOdd <= Jyougen)
            return Array.BinarySearch(SosuuArr, (int)pTargetOdd) >= 0;

        for (long I = 3; I * I <= pTargetOdd; I += 2)
            if (pTargetOdd % I == 0) return false;
        return true;
    }
}

実行結果

数列の初項の上限を、16000000として検証します
解は15514861で、数列は
  15514861
  31029721
  62059441
 124118881
 248237761
 496475521
 992951041
1985902081
経過時間=00:00:15.0657181

解説

数列の初項の上限を決めて、求まった解を検証してます。