Project Euler : Problem 30 『Digit fifth powers』

Red Spotted Purple / DrPhotoMoto

問題

projecteuler.net

　ちょうどいいProject Euler問題文翻訳サイトがあったので、そっちにリンク張っておきます。
Problem 30 - PukiWiki

最大値をある程度予測する

　(含まれないけど)一番小さいのは\( 1 = 1^{5} \)。
じゃぁ一番大きい桁はいくらだろうか？

　例えば9⁵の解は59045。
これだけで式は5桁分必要になるのがわかる。
じゃぁ9⁵を5回加えるといくらになるか？
\( 5 \times 9^{5} = 295245 \)
桁が増えて6桁になった……。

　じゃぁ6桁ではどうか。
\( 6 \times 9^{5} = 354294 \)
354294は999999より小さい
よって、6桁まで計算すれば十分という事が分かった。

式を整理する

　0 ≦ a, b, c, d, e, f ≦ 9 として、
\( 10^{5}a+10^{4}b+10^{3}c+10^{2}d+10^{1}e+10^{0}f = a^{5}+b^{5}+c^{5}+d^{5}+e^{5}+f^{5} \\
10^{5}a - a^{5} +10^{4}b - b^{5}+10^{3}c - c^{5}+10^{2}d - d^{5}+10^{1}e - e^{5}+10^{0}f - f^{5} = 0 \\
a(10^{5} - a^{4}) +b(10^{4} - b^{4})+c(10^{3} - c^{4})+d(10^{2} - d^{4})+e(10^{1} - e^{4})+f(10^{0} - f^{4}) = 0\)
この式に対して(a, b, c, d, e, f) = (0, 0, 0, 0, 0, 0)から(9, 9, 9, 9, 9, 9)を代入して0になったら成立。
無駄も多いけど、とりあえず動かしてみて遅すぎたら考え直す方針で。

コード

using System;
using System.Diagnostics;

namespace Problem30
{
    class Program
    {
        static void Main(string[] args)
        {
            Debug.WriteLine(DigitFifthPowers());
        }

        static Int64 DigitFifthPowers()
        {
            Int64 sum = 0;

            for (int a = 0; a < 10; a++)
            {
                Int64 A = Part(a, 5);
                for (int b = 0; b < 10; b++)
                {
                    Int64 B = Part(b, 4);
                    for (int c = 0; c < 10; c++)
                    {
                        Int64 C = Part(c, 3);
                        for (int d = 0; d < 10; d++)
                        {
                            Int64 D = Part(d, 2);
                            for (int e = 0; e < 10; e++)
                            {
                                Int64 E = Part(e, 1);

                                for (int f = 0; f < 10; f++)
                                {
                                    Int64 F = Part(f, 0);

                                    if (A + B + C + D + E + F == 0)
                                    {
                                        Int64 n = Number(a, b, c, d, e, f);

                                        sum += n;
                                    }
                                }
                            }
                        }
                    }
                }
            }

            //1 = 1^5 が含まれるので1引く
            return sum - 1;
        }

        /// <summary>
        /// 項の塊(要素？)を処理する
        /// </summary>
        static Int64 Part(int n, int y)
        {
            return (Int64)(n * (Math.Pow(10, y) - Math.Pow(n, 4)));
        }

        /// <summary>
        /// 桁ごとにバラってるのを１つの数にする
        /// </summary>
        static Int64 Number(params int[] d)
        {
            Int64 n = 0;

            for (int i = 0; i < d.Length; i++)
            {
                n += (Int64)(d[i] * (Math.Pow(10, d.Length - i - 1)));
            }

            return n;
        }
    }
}