Problem25 フィボナッチ数列で1000桁になる最初の項番号

問題

フィボナッチ数列は以下の漸化式で定義される

Fn = Fn-1 + Fn-2, ただし F1=1 , F2=1
最初の12項は以下である.

F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34
F10 = 55
F11 = 89
F12 = 144
12番目の項, F12が3桁になる最初の項である.

1000桁になる最初の項番号を答えよ

ソース

using System;

class Program
{
    //const int TargetKeta = 3;
    const int TargetKeta = 1000;

    static void Main()
    {
        int[,] IntArr = new int[4800, TargetKeta * 2];
        IntArr[2, 0] = IntArr[1, 0] = 1;

        for (int N = 3; N <= IntArr.GetUpperBound(0); N++) {
            for (int I = 0; I <= IntArr.GetUpperBound(1); I++) {
                IntArr[N, I] = IntArr[N - 2, I] + IntArr[N - 1, I];
            }
            for (int I = 0; I <= IntArr.GetUpperBound(1); I++) {
                if (IntArr[N, I] >= 10) {
                    IntArr[N, I + 1] += IntArr[N, I] / 10;
                    IntArr[N, I] %= 10;
                }
            }
            var sb = new System.Text.StringBuilder();
            bool IsHit = false;
            for (int Y = IntArr.GetUpperBound(1); Y >= 0; Y--) {
                if (IsHit == false && IntArr[N, Y] > 0) {
                    IsHit = true;
                }
                if (IsHit) sb.Append(IntArr[N, Y]);
            }
            Console.WriteLine("{0}番目の値は{1}桁({2})", N, sb.Length, sb.ToString());
            if (sb.Length >= TargetKeta) return;
        }
    }
}

実行結果

省略
4782番目の値は1000桁(10700662663827589367649805844573968850836838966321516650132
35203375314520604694040621889147582489792657804694888177591957484336466672569959
51299603046126274809248218614406943305123477444275027378175308757939166619214925
91867595539664228371489431130746995034395470019854326097230672901928705264472437
26117715821825548491120525013201478612965931381792235559657452039506137551467837
54322911960212993404826070617539770684706820289548690266618543512452190036948064
13574474709117076197669456910700980243934396174741037369125032313655321647736970
23167755051595173518460579954919410967778373229665796581646513903488154256310184
22419025984608800011018625555024549393711365165703944762958471454852342595042858
24253060835444354282126110089928637950480068943303097732178348645431132057656598
68456288616808718693835297350643986297640660000723562917905207051164077614812491
88583094594056668833910935094445657635766615161931775379289166158132715961687748
7983821820492520348473874384736771934512787029218636250627816)

解説

Intの配列で大きい桁の変数を代用してます。