Problem74 桁の階乗による連鎖

問題

145は各桁の階乗の和が145と自分自身に一致することで有名である.

1! + 4! + 5! = 1 + 24 + 120 = 145

169の性質はあまり知られていない.
これは169に戻る数の中で最長の列を成す.
このように他の数を経て自分自身に戻るループは3つしか存在しない.

169 → 363601 → 1454 → 169
871 →  45361 →  871
872 →  45362 →  872

どのような数からスタートしてもループに入ることが示せる.

例を見てみよう.

 69 → 363600 → 1454 →   169 → 363601 → 1454
 78 →  45360 →  871 → 45361 →    871
540 →    145 →  145

69から始めた場合, 列は5つの循環しない項を持つ.
また100万未満の数から始めた場合、最長の循環しない項は60個であることが知られている.

100万未満の数から開始する列の中で, 60個の循環しない項を持つものはいくつあるか?

ソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        //foreach (int EachInt in new int[] { 145, 169, 871, 872, 69, 78, 540 }) {
        //    Console.WriteLine("{0}の循環しない項は{1}", EachInt, DeriveKousuu(EachInt));
        //    Console.WriteLine();
        //}

        var sw = System.Diagnostics.Stopwatch.StartNew();
        int AnswerCnt = 0;
        for (int I = 1; I <= 999999; I++) {
            if (I % 50000 == 0) {
                Console.WriteLine("{0}をチェック中。AnswerCnt={1}。経過時間={2}", I, AnswerCnt, sw.Elapsed);
            }
            if (DeriveKousuu(I) == 60) AnswerCnt++;
        }
        Console.WriteLine("Answer={0}", AnswerCnt);
    }

    static int DeriveKousuu(int pTarget)
    {
        var ValList = new List<int>();
        ValList.Add(pTarget);

        int CurrVal = pTarget;
        //Console.Write("{0}", CurrVal);

        while (true) {
            int NextVal = 0;
            foreach (char EachChar in CurrVal.ToString()) {
                NextVal += CalcKaijyo(EachChar - '0');
            }
            //Console.Write("→{0}", NextVal);

            if (ValList.Contains(NextVal)) {
                //Console.WriteLine();
                return ValList.Count;
            }
            else ValList.Add(NextVal);

            CurrVal = NextVal;
        }
    }

    static Dictionary<int, int> mKaijyoDict = new Dictionary<int, int>();
    static int CalcKaijyo(int pN)
    {
        if (mKaijyoDict.ContainsKey(pN))
            return mKaijyoDict[pN];

        int WillReturn = 1;
        for (int I = 2; I <= pN; I++) {
            WillReturn *= I;
        }
        return mKaijyoDict[pN] = WillReturn;
    }
}

実行結果

省略
700000をチェック中。AnswerCnt=282。経過時間=00:00:59.8240080
750000をチェック中。AnswerCnt=330。経過時間=00:01:03.9670251
800000をチェック中。AnswerCnt=342。経過時間=00:01:08.2473174
850000をチェック中。AnswerCnt=342。経過時間=00:01:12.5488490
900000をチェック中。AnswerCnt=342。経過時間=00:01:16.9981156
950000をチェック中。AnswerCnt=390。経過時間=00:01:21.5248887
Answer=402

解説

配列の初期化を使った下記の記述で事前検証してます。

foreach (int EachInt in new int[] { 145, 169, 871, 872, 69, 78, 540 }) {
    Console.WriteLine("{0}の循環しない項は{1}", EachInt, DeriveKousuu(EachInt));
    Console.WriteLine();
}