Cマガ電脳クラブ(第077回) もとどおり数

問題

たとえば、17を3乗する。
　17の3乗 = 4913
この右辺を1桁ずつに分けて、足し合わせる。
　4+9+1+3=17
すると、3乗する前の17に戻った。

このように、「PをQ乗した数の各桁の数字の和をとるとPになる」
という条件を満たすPとQの組み合わせを見ていくと、
Q＝2のときは、P＝9のときしか成立しない。

では、ひとつのPでしか上記の条件が成立しない、Q＝2の次に小さいQを見つけてほしい。
ただし、P、Qは2以上の整数とする(P＝1ではすべて成立してしまう)。

ソース

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

class Program
{
    const int LimitQ = 15;

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

        for (long Q = 3; Q <= LimitQ; Q++) {
            Console.WriteLine(new string('■', 30));
            long LimitP = DeriveLimitP(Q);
            var MotodooriSuuList = new List<long>();
            for (long P = 2; P <= LimitP; P++) {
                if (IsMotodooriSuu(P, Q) == false) continue;
                MotodooriSuuList.Add(P);
                if (MotodooriSuuList.Count > 1) break;
            }
            if (MotodooriSuuList.Count == 1) {
                Console.WriteLine(new string('■', 30));
                Console.WriteLine("Answer={0}", Q);
                break;
            }
        }
        Console.WriteLine("経過時間={0}", sw.Elapsed);
    }

    //Qを引数をして、Pの上限を求める
    static long DeriveLimitP(long pQ)
    {
        Console.WriteLine("Q={0}の場合の、検索するPの上限を求めます。", pQ);
        for (long Ketasuu = 1; ; Ketasuu++) {
            long wkMin = DeriveMin(Ketasuu);
            long wkMax = DeriveMax(Ketasuu);

            Console.WriteLine("Pが{0}桁の場合、Pの最小値={1}、Pの最大値={2}",
                Ketasuu, wkMin, wkMax);

            long wkKetasuu = (long)Math.Truncate(pQ * Math.Log10(wkMax)) + 1;
            Console.WriteLine("{0}の{1}乗の桁数={2}で、各桁の数字の和の最大は、{2}*9で{3}",
                wkMax, pQ, wkKetasuu, 9 * wkKetasuu);

            if (wkMin > 9 * wkKetasuu) {
                //1桁小さい数の最大値までチェックすればOK
                long WillReturn = DeriveMax(Ketasuu - 1);
                Console.WriteLine("Q={0}での、検証するPの上限={1}", pQ, WillReturn);
                return WillReturn;
            }
        }
    }

    //指定桁での最小値を求める
    static long DeriveMin(long pKetaSuu)
    {
        return (long)Math.Pow(10, pKetaSuu - 1);
    }

    //指定桁での最大値を求める
    static long DeriveMax(long pKetaSuu)
    {
        return (long)Math.Pow(10, pKetaSuu) - 1;
    }

    //PのQ乗が、もとどおり数かを返す
    static bool IsMotodooriSuu(long pP, long pQ)
    {
        if (IsMotodooriSuuHelper(pP, pQ) == false) return false;

        long[] wkLongArr = new long[9999];
        long CurrKeta = 1;
        long CopiedP = pP;
        while (CopiedP > 0) {
            wkLongArr[CurrKeta++] = CopiedP % 10;
            CopiedP /= 10;
        }

        for (int I = 1; I <= pQ - 1; I++) {
            for (int J = 1; J <= wkLongArr.GetUpperBound(0); J++) {
                wkLongArr[J] *= pP;
            }
            for (int J = 1; J <= wkLongArr.GetUpperBound(0); J++) {
                if (wkLongArr[J] >= 10) {
                    wkLongArr[J + 1] += wkLongArr[J] / 10;
                    wkLongArr[J] %= 10;
                }
            }
        }
        //添字の0番目を消す
        wkLongArr = wkLongArr.Skip(1).ToArray();

        if (wkLongArr.Sum() == pP) {
            string[] wkStrArr = Array.ConvertAll(wkLongArr, X => X.ToString());
            string wkStr = string.Concat(wkStrArr);
            wkStr = new string(wkStr.Reverse().ToArray());
            Console.WriteLine("{0,3}の{1,2}乗={2}はもとどおり数です",
                pP, pQ, wkStr.TrimStart('0'));
            return true;
        }
        return false;
    }

    //PのQ乗が、もとどおり数かを返す
    static bool IsMotodooriSuuHelper(long pP, long pQ)
    {
        //PのQ乗 = Pの各桁の和 であることの必要条件
        //PのQ乗 Mod 9 = Pの各桁の和 Mod 9
        //を満たすかを九去法で判定
        long BekijyouMod9 = pP % 9;
        for (long I = 2; I <= pQ; I++) {
            BekijyouMod9 *= pP;
            BekijyouMod9 %= 9;
        }
        return pP % 9 == BekijyouMod9;
    }
}

実行結果

省略
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
Q=12の場合の、検索するPの上限を求めます。
Pが1桁の場合、Pの最小値=1、Pの最大値=9
9の12乗の桁数=12で、各桁の数字の和の最大は、12*9で108
Pが2桁の場合、Pの最小値=10、Pの最大値=99
99の12乗の桁数=24で、各桁の数字の和の最大は、24*9で216
Pが3桁の場合、Pの最小値=100、Pの最大値=999
999の12乗の桁数=36で、各桁の数字の和の最大は、36*9で324
Pが4桁の場合、Pの最小値=1000、Pの最大値=9999
9999の12乗の桁数=48で、各桁の数字の和の最大は、48*9で432
Q=12での、検証するPの上限=999
108の12乗=2518170116818978404827136はもとどおり数です
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
Answer=12
経過時間=00:00:05.1123218

解説

Pを1桁とすると、Pの最小値は  1、最大値は  9で、その3乗は      729で3桁であり、3*9=27
Pを2桁とすると、Pの最小値は 10、最大値は 99で、その3乗は   970299で6桁であり、6*9=54
Pを3桁とすると、Pの最小値は100、最大値は999で、その3乗は997002999で9桁であり、9*9=81

Pが1桁増えた際の増分は、9,90,900,9000なのに対し、
PのQ乗の桁数の増分はQとなります。(対数法則 Log10(Mのp乗) = p*Log10(M) で変換)

なので、指定桁でのPの最小値 > (Pの最大値のQ乗の桁数)*9
になったら、Qを固定した時の、Pの上限としてます。