Project Euler : Problem 34 『Digit factorials』

問題

projecteuler.net
日本語訳→Problem 34 - PukiWiki

総当たりでええやん。でも上限は……？

　総当たりでいいけど、上限と下限を決める必要がある。
下限は3で決まりなんだけど、上限は次のように考えて決めた。

　まず、d桁の9(99とか9999とか)で作られる数nはこう書ける
$n = 10^{d}-1$
次に、nの各桁の階乗の和sumはこう書ける
$sum = d \times 9!$

　例えばn = 99(2桁)の場合だと、
$n = 99 = 10^{2}-1$
$sum = 2 \times 9! = 725760$
こんな感じになる。

　見ての通り、sumの方が圧倒的に大きい。
しかし桁数dを増やしていくと、片やd倍に対して片やd桁の勢いで増えていくので、どこかでsum < nになるはず。
つまり、ある桁数d以上はsum = nにならないということ。
そういう桁数dを見つければ探索の上限を $10^{d}-1$ に決めることができる。*1

コード

using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace Problem34
{
    class Program
    {
        static void Main(string[] args)
        {
            P34 p = new P34();
            Debug.WriteLine(p.Solve());
        }
    }

    class P34
    {
        //階乗
        Dictionary<int, int> factrial;

        /// <summary>
        /// コンストラクタ
        /// </summary>
        public P34()
        {
            this.SetFactrial();
        }

        /// <summary>
        /// 階乗の値をセットする
        /// </summary>
        private void SetFactrial()
        {
            this.factrial = new Dictionary<int, int>();

            this.factrial[0] = 1;
            for (int i = 1; i < 10; i++)
            {
                this.factrial[i] = this.factrial[i - 1] * i;
            }
        }

        /// <summary>
        /// 問題を解く
        /// </summary>
        public int Solve()
        {
            int answer = 0;
            int upperLimit = this.GetUpperLimit();

            //問題文より、1!と2!は含まないので3!から
            for (int num = 3; num < upperLimit; num++)
            {
                if (num == this.SumDigitsFactrial(num))
                    answer += num;
            }

            return answer;
        }

        /// <summary>
        /// 探索する値の最大値
        /// </summary>
        private int GetUpperLimit()
        {
            int d = 1;

            //9がd桁並んでいるとすると(10^d)-1と書ける
            //d*9!が(10^d)-1より小さくなるdを見つければ、(10^d)-1以上を調べる必要は無くなる
            while (Math.Log10(d*factrial[9]+1) >= d)
            {
                d++;
            }

            return d*factrial[9];
        }

        /// <summary>
        /// 各桁を階乗し、総和を求める
        /// </summary>
        private int SumDigitsFactrial(int num)
        {
            int sum = 0;

            foreach(char c in num.ToString())
            {
                sum += this.factrial[(int)(c - '0')];
            }

            return sum;
        }

    }
}