ProjectEuler30

gistfile1.cs

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

namespace ProjectEuler30
{
    class MainClass
    {
        /*
         * 驚くべきことに, 各桁を4乗した数の和が元の数と一致する数は3つしかない.
         * 
         * 1634 = 1^4 + 6^4 + 3^4 + 4^4
         * 8208 = 8^4 + 2^4 + 0^4 + 8^4
         * 9474 = 9^4 + 4^4 + 7^4 + 4^4
         * ただし, 1=1^4は含まないものとする. この数たちの和は 1634 + 8208 + 9474 = 19316 である.
         * 
         * 各桁を5乗した数の和が元の数と一致するような数の総和を求めよ.
         */ 
        const int EXPONENT = 5;
        static readonly int[] POWER5 = {
            0, 1,
            (int)Math.Pow(2, EXPONENT),
            (int)Math.Pow(3, EXPONENT),
            (int)Math.Pow(4, EXPONENT),
            (int)Math.Pow(5, EXPONENT),
            (int)Math.Pow(6, EXPONENT),
            (int)Math.Pow(7, EXPONENT),
            (int)Math.Pow(8, EXPONENT),
            (int)Math.Pow(9, EXPONENT)
        };

        /*
         * ** My Algorithm **
         * いくつまで調べればいいのか分からないので，制約条件を考える．
         * 単純に考えれば，n桁の値は[10^(n-1), 10^n)の範囲にあり，n桁の各位の5乗和は[1, n*(9^5)]の範囲にある．
         * (d/dn){n^(9^5)} = 9^5, (d/dn){10^(n-1)} = log10 * 10^(n-1)から，十分nが大きくなると後者の変化量が大きくなる．
         * つまり，十分nが大きくなると，(n桁の値の最小値)>(n桁の各位の5乗和の最大値)になり，n桁以上の値を調べても意味はない．(数学的には本当に厳密にやるとすると十分大きいあるnで(n桁の値の最小値)>(n桁の各位の5乗和の最大値)を示さないといけないが面倒なのでパス)
         * 9^5 <= log10 * 10^(n-1)となるnはn>=6で，n>=6以上で(n桁の値の最小値)>(n桁の各位の5乗和の最大値)となる最小のnを求めれば，[2, (10^n) - 1]の範囲だけ調べたら良いことが分かる．
         */
        public static void Main(string[] args)
        {
            List<int> equalValues = new List<int>();

            int over_digits = GetOverDigits();
            Console.WriteLine(string.Format("n:{0}", over_digits));
            int max_value = (int)Math.Pow(10, over_digits) - 1;
            for (int i = 2; i < max_value; i++) {
                int tmp = i;
                int sum_power5 = 0;
                while (tmp != 0) {
                    sum_power5 += POWER5[tmp % 10];
                    tmp /= 10;
                }

                if (i == sum_power5) { equalValues.Add(i); }
            }

            Console.WriteLine(equalValues.Sum());
        }

        // calculate min(n>=6)[n*9^5 < 10^(n-1)]
        public static int GetOverDigits()
        {
            int n = 6;
            int left = n * POWER5[9];
            int right = (int)Math.Pow(10, n - 1);

            while (left >= right) {
                n++;
                left += POWER5[9];
                right *= 10;
            }

            return n;
        }
    }
}

// n:7
// 443839