Cマガ電脳クラブ(第126回) 開き直り数

問題

3435という数は、1桁ずつに分けて、それぞれの数を自分と同じ数でべき乗して足し合わせると、元の数である3435になる。
  3435 ＝ 3の3乗 + 4の4乗 + 3の3乗 + 5の5乗
このような数を“開き直り数”と呼ぶことにする。ちょっと考えれば1(=1の1乗)もこの種の数であることがわかる。
では1以上の整数で、この1と3435以外の開き直り数をすべて見つけていただきたい。
ただし、ここでは0の0乗は0とする。

ソース

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

class Program
{
    struct JyoutaiDef
    {
        internal long CurrNum;
        internal List<long> NumList;
    }

    static void Main()
    {
        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        for (long I = 0; I <= 9; I++) {
            WillPush.CurrNum = I;
            WillPush.NumList = new List<long>() { I };
            stk.Push(WillPush);
        }
        var HirakiNaoriSuuList = new List<long>();
        while (stk.Count > 0) {
            JyoutaiDef Popped = stk.Pop();

            //開き直り数かを判定
            long wkHirakiNaoriSuu;
            if (IsHirakiNaoriSuu(Popped.NumList, out wkHirakiNaoriSuu)) {
                HirakiNaoriSuuList.Add(wkHirakiNaoriSuu);
            }

            //枝切り
            if (Popped.NumList.Count >= 10) continue;

            for (long I = Popped.CurrNum; I <= 9; I++) {
                WillPush.CurrNum = I;
                WillPush.NumList = new List<long>(Popped.NumList) { I };
                stk.Push(WillPush);
            }
        }
        HirakiNaoriSuuList.RemoveAll(X => X < 1); //1未満は不適
        HirakiNaoriSuuList.Sort();
        HirakiNaoriSuuList.ForEach(X => Console.WriteLine(X));
    }

    //開き直り数かを判定
    static bool IsHirakiNaoriSuu(List<long> pNumList, out long pHirakiNaoriSuu)
    {
        pHirakiNaoriSuu = -1;

        long BekijyouSum = 0;
        pNumList.ForEach(X => BekijyouSum += DeriveBekijyou(X));
        List<long> SumNumList = DeriveNumList(BekijyouSum);

        if (pNumList.Count != SumNumList.Count) return false;

        var tmp1 = pNumList.OrderBy(X => X);
        var tmp2 = SumNumList.OrderBy(X => X);
        if (tmp1.SequenceEqual(tmp2)) {
            pHirakiNaoriSuu = BekijyouSum;
            return true;
        }
        return false;
    }

    //べき乗を求める
    static long DeriveBekijyou(long pNum)
    {
        if (pNum == 0) return 0;
        long WillReturn = 1;
        for (long I = 1; I <= pNum; I++) {
            WillReturn *= pNum;
        }
        return WillReturn;
    }

    //数値から数字のListを求めて返す
    static List<long> DeriveNumList(long pVal)
    {
        var WillReturn = new List<long>();
        long CopiedVal = pVal;
        do {
            long ModVal = CopiedVal % 10;
            WillReturn.Add(ModVal);
            CopiedVal /= 10;
        } while (CopiedVal > 0);
        return WillReturn;
    }
}

実行結果

1
3435
438579088

解説

9の9乗=387420489 であり、
387420489 *  1 =  387420489
387420489 *  2 =  774840978
387420489 *  3 = 1162261467
387420489 *  4 = 1549681956
387420489 *  5 = 1937102445
387420489 *  6 = 2324522934
387420489 *  7 = 2711943423
387420489 *  8 = 3099363912
387420489 *  9 = 3486784401
387420489 * 10 = 3874204890
387420489 * 11 = 4261625379
387420489 * 12 = 4649045868
387420489 * 13 = 5036466357
387420489 * 14 = 5423886846
387420489 * 15 = 5811307335
なので、10桁以下であることが、開き直り数である必要条件です。

0から9の数を重複を許して、10個まで用意して、
それぞれのべき乗の和が、開き直り数かを調べてます。

9H10 = (9+10-1)C10 = 18C8 = 43758
なので1から3874204890までループさせるよりも、計算量が少ないです。

第001回 10桁の数の怪