Cマガ電脳クラブ(第001回) 10桁の数の怪

問題

ある10桁の数を考えていただきたい。もちろん、そこには10個の数字が並んでいる。
その数は、「構成する各数字をそれぞれ10乗したものの和」に等しいという。その数はいくつか？

たとえば、以下の式は成立しない。残念ながら右辺が1だけ大きいのだ。
1136483324 = 1の10乗 + 1の10乗 + 3の10乗 + 6の10乗 + 4の10乗 + 8の10乗 + 3の10乗 + 3の10乗 + 2の10乗 + 4の10乗

ソース(力まかせ法)

using System;

class Program
{
    static void Main()
    {
        var sw = System.Diagnostics.Stopwatch.StartNew();

        long Sum10Jyou = 0L;
        long KasanVal = 1;
        for (long I = 1000000000L; I <= 9999999999L; I += KasanVal) {
            if (I % 500000000L == 1L) Console.WriteLine("{0}。{1}をチェック中", sw.Elapsed, I);

            if (I % 10 == 0) {
                Sum10Jyou = DeriveSum10Jyou(I);
            }
            else { //1桁目の差分を加算
                Sum10Jyou -= Get10Jyou(I % 10L - 1L);
                Sum10Jyou += Get10Jyou(I % 10L);
            }

            KasanVal = 1L;
            if (I == Sum10Jyou) Console.WriteLine("Answer={0}", I);
            else if (I < Sum10Jyou) {
                //1桁目が0になるまでスキップ
                KasanVal = 10L - I % 10L;
            }
        }
    }

    static long DeriveSum10Jyou(long pTarget)
    {
        long SavedTarget = pTarget;
        long Sum10Jyou = 0L;
        do {
            long ModVal = pTarget % 10L;
            Sum10Jyou += Get10Jyou(ModVal);
            if (SavedTarget < Sum10Jyou) return Sum10Jyou;
            pTarget /= 10L;
        } while (pTarget > 0L);
        return Sum10Jyou;
    }

    static long Get10Jyou(long pTarget)
    {
        if (pTarget == 1L) return 1L;
        if (pTarget == 2L) return 1024L;
        if (pTarget == 3L) return 59049L;
        if (pTarget == 4L) return 1048576L;
        if (pTarget == 5L) return 9765625L;
        if (pTarget == 6L) return 60466176L;
        if (pTarget == 7L) return 282475249L;
        if (pTarget == 8L) return 1073741824L;
        if (pTarget == 9L) return 3486784401L;
        return 0L;
    }
}

ソース(数字の組み合わせを列挙して、それらの10乗の和を求める方法)

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

class Program
{
    struct JyoutaiDef
    {
        internal int CurrVal;
        internal List<int> ValList;
    }

    static void Main()
    {
        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        for (int I = 0; I <= 9; I++) {
            WillPush.CurrVal = I;
            WillPush.ValList = new List<int>() { I };
            stk.Push(WillPush);
        }

        while (stk.Count > 0) {
            JyoutaiDef Popped = stk.Pop();

            if (Popped.ValList.Count == 10) {
                long Sum10Jyou = 0;
                foreach (int AnyInt in Popped.ValList)
                    Sum10Jyou += Get10Jyou(AnyInt);
                
                //10桁であること
                if ((1000000000L <= Sum10Jyou && Sum10Jyou <= 9999999999L) == false)
                    continue;

                //数字の使用回数が一致していること
                IEnumerable<int> wkEnum = Sum10Jyou.ToString().ToCharArray().
                    Select(X => int.Parse(X.ToString())).OrderBy(X => X);
                if (wkEnum.SequenceEqual(Popped.ValList.OrderBy(X => X))) {
                    Console.WriteLine("Answer={0}", Sum10Jyou);
                }
                continue;
            }

            for (int I = Popped.CurrVal; I <= 9; I++) {
                WillPush.CurrVal = I;
                WillPush.ValList = new List<int>(Popped.ValList) { I };
                stk.Push(WillPush);
            }
        }
    }

    static long Get10Jyou(int pTarget)
    {
        if (pTarget == 1) return 1L;
        if (pTarget == 2) return 1024L;
        if (pTarget == 3) return 59049L;
        if (pTarget == 4) return 1048576L;
        if (pTarget == 5) return 9765625L;
        if (pTarget == 6) return 60466176L;
        if (pTarget == 7) return 282475249L;
        if (pTarget == 8) return 1073741824L;
        if (pTarget == 9) return 3486784401L;
        return 0L;
    }
}

実行結果

00:00:00.0006210。1000000001をチェック中
00:00:59.8395868。1500000001をチェック中
00:02:00.4806814。2000000001をチェック中
00:03:17.4356782。2500000001をチェック中
00:04:31.0162255。3000000001をチェック中
00:05:57.0148923。3500000001をチェック中
00:07:24.0376388。4000000001をチェック中
00:09:12.7531839。4500000001をチェック中
Answer=4679307774
00:10:58.1672008。5000000001をチェック中
00:13:03.9637828。5500000001をチェック中
00:15:03.1932723。6000000001をチェック中
00:17:14.8784219。6500000001をチェック中
00:19:17.4409099。7000000001をチェック中
00:21:30.5686557。7500000001をチェック中
00:23:40.8811793。8000000001をチェック中
00:25:56.0425442。8500000001をチェック中
00:28:09.4392885。9000000001をチェック中
00:30:18.3545992。9500000001をチェック中

解説

for文の中で、
10で割った剰余が1以上だったら、1桁目の差分を加算することにより
計算量を減らしてます。

数字の組み合わせを列挙して、それらの10乗の和を求める方法だと
劇的に高速化されて1秒もかからず答えが求まります。