Cマガ電脳クラブ(第114回) 循環する数列

問題

次のような漸化式で表される数列がある。
 a(n+1)=f(a(n))−a(n)

ここで、f(x)は、xを構成する数字を降順に(大きな数字から順に)並べ替える関数である。
つまり｢整数a(n)を降順に並べ替えたものからa(n)を引いたものをa(n+1)とする｣ということだ
(各項は0以上の整数であることとする)。
たとえば、a(0)=547とすると，a(1)=754-547=207、a(2)=720-207=513、・・・となる。

この例の場合、a(5)で0になってしまうが、次の例のように、循環する場合もある。
　3996, 5967, 3798, 6075, 1575, 5976, 3789, 6084, 2556
この2556の次は3996に戻る。
この循環は9個の相異なる数で構成されているが、
では、これよりも長い、つまり10個以上の数で構成される循環をひとつお答えいただきたい。

ソース

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

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

        //数字を入れ替えての引き算なので、a1は9の倍数であり、
        //同様にa2もa3も9の倍数となる。
        //a0に循環するのだから、a0が9の倍数であることは必要条件である。
        for (int I = 0; I < int.MaxValue; I += 9) {
            if (I % 900000 == 0)
                Console.WriteLine("{0}を調査中。経過時間={1}", I, sw.Elapsed);

            var KouList = new List<int>();
            KouList.Add(I);

            bool HasJyunkan = false;
            int SyokouKetasuu = DeriveKetasuu(I);
            while (true) {
                int NextKou = DeriveNextKou(KouList.Last());

                //桁数が増えることのない漸化式なので
                //桁数が減ったら循環しない。よって枝切りできる。
                if (SyokouKetasuu > DeriveKetasuu(NextKou))
                    break;

                if (KouList.Contains(NextKou)) {
                    HasJyunkan = (KouList[0] == NextKou);
                    break;
                }
                KouList.Add(NextKou);
            }
            if (HasJyunkan && KouList.Count >= 10) {
                Console.WriteLine("解を発見。経過時間={0}", sw.Elapsed);
                for (int A = 0; A <= KouList.Count - 1; A++) {
                    Console.WriteLine("A({0})={1}", A, KouList[A]);
                }
                break;
            }
        }
    }

    //漸化式を使って次の項を求める
    static int DeriveNextKou(int pCurrKou)
    {
        return DeriveSortedNum(pCurrKou) - pCurrKou;
    }

    //構成する数字を降順に並べ替えた数値を返す
    static int DeriveSortedNum(int pTargetNum)
    {
        var NumList = new List<int>();

        int CopiedVal = pTargetNum;
        do {
            int ModVal = CopiedVal % 10;
            NumList.Add(ModVal);
        } while ((CopiedVal /= 10) > 0);
        NumList.Sort((a, b) => b.CompareTo(a));

        int SortedNum = 0;
        foreach (int EachNum in NumList) {
            SortedNum *= 10;
            SortedNum += EachNum;
        }
        return SortedNum;
    }

    //桁数を求める
    static int DeriveKetasuu(int pTargetNum)
    {
        if (pTargetNum < 10) return 1;
        if (pTargetNum < 100) return 2;
        if (pTargetNum < 1000) return 3;
        if (pTargetNum < 10000) return 4;
        if (pTargetNum < 100000) return 5;
        if (pTargetNum < 1000000) return 6;
        if (pTargetNum < 10000000) return 7;
        if (pTargetNum < 100000000) return 8;
        return 9;
    }
}

実行結果

省略
10800000を調査中。経過時間=00:00:25.6233968
11700000を調査中。経過時間=00:00:28.7240459
12600000を調査中。経過時間=00:00:31.8483555
13500000を調査中。経過時間=00:00:35.0265435
解を発見。経過時間=00:00:37.1874889
A(0)=14100507
A(1)=61310493
A(2)=35122617
A(3)=41409594
A(4)=58134816
A(5)=30519495
A(6)=69034815
A(7)=29619495
A(8)=70345926
A(9)=27308394
A(10)=71434926
A(11)=26209395
A(12)=73443825

解説

初項は9の倍数であるという必要条件を使って、計算量を減らしてます。