Problem63 べき乗の桁の個数

問題

5桁の数 16807 = 7の5乗は、自然数を5乗した数である.
同様に9桁の数 134217728 = 8の9乗も自然数を9乗した数である.

自然数をn乗して得られるn桁の正整数は何個あるか?

ソース

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var AnswerSet = new HashSet<string>();

        for (int n = 1; n <= 9; n++) {
            int[] ValArr = new int[30];
            ValArr[0] = 1;

            for (int a = 1; a < int.MaxValue; a++) {
                for (int I = 0; I <= ValArr.GetUpperBound(0) - 1; I++) {
                    ValArr[I] *= n;
                }

                for (int I = 0; I <= ValArr.GetUpperBound(0) - 1; I++) {
                    if (ValArr[I] > 9) { //繰り上がりの処理
                        ValArr[I + 1] += ValArr[I] / 10;
                        ValArr[I] %= 10;
                    }
                }

                var sb = new System.Text.StringBuilder();
                bool AppearNonZero = false;
                for (int I = ValArr.GetUpperBound(0); I >= 0; I--) {
                    if (ValArr[I] != 0) AppearNonZero = true;
                    if (AppearNonZero) sb.Append(ValArr[I]);
                }

                if (sb.Length == a) {
                    Console.WriteLine("{0}の{1}乗={2}が{1}桁の数", n, a, sb.ToString(), a);
                    AnswerSet.Add(sb.ToString());
                }
                else break;
            }
        }
        Console.WriteLine("自然数をn乗して得られるn桁の正整数は{0}個", AnswerSet.Count);
    }
}

実行結果

省略
8の8乗=16777216が8桁の数
8の9乗=134217728が9桁の数
8の10乗=1073741824が10桁の数
9の1乗=9が1桁の数
9の2乗=81が2桁の数
9の3乗=729が3桁の数
9の4乗=6561が4桁の数
9の5乗=59049が5桁の数
9の6乗=531441が6桁の数
9の7乗=4782969が7桁の数
9の8乗=43046721が8桁の数
9の9乗=387420489が9桁の数
9の10乗=3486784401が10桁の数
9の11乗=31381059609が11桁の数
9の12乗=282429536481が12桁の数
9の13乗=2541865828329が13桁の数
9の14乗=22876792454961が14桁の数
9の15乗=205891132094649が15桁の数
9の16乗=1853020188851841が16桁の数
9の17乗=16677181699666569が17桁の数
9の18乗=150094635296999121が18桁の数
9の19乗=1350851717672992089が19桁の数
9の20乗=12157665459056928801が20桁の数
9の21乗=109418989131512359209が21桁の数
自然数をn乗して得られるn桁の正整数は49個

解説

10以上の桁だと、下記のように
桁の最大値よりも増分が大きいので9以下の自然数のみでべき乗値をチェックしてます。

10の1乗=  10  (1桁の数の最大値は  9)
10の2乗= 100  (2桁の数の最大値は 99)
10の3乗=1000  (3桁の数の最大値は999)

また、桁数ごとの最小値は、
下記のように10倍ずつ増えていくので、9以下の自然数でn桁の最小値以下だったら、
もう追いつけないので、Break文を記述してます。

1桁の最小値は0
2桁の最小値は10
3桁の最小値は100
4桁の最小値は1000