Cマガ電脳クラブ(第026回) 社交鎖

問題

Xの約数(ただし、自分自身は除く)の和を求める関数をf(X)とする。
いま、X1, X2, ・・・Xnという、n個の数の列があり、次の式が成り立っている。
　X2=f(X1)
　X3=f(X2)
　・・・
　Xn=f(X(n-1))
　X1=f(X(n)
つまり、それぞれの数の約数の和が、数の列の次の数になっていて、最後の数の約数の和が、最初の数になっている。
こういった数の列の輪を「社交鎖」という。

この鎖がふたつの数で構成される場合 (n=2) の例を示そう。
220と284は、それぞれ自分自身を除く約数の和が相手の数になっている。
220=2×2×5×11で、その約数は1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110であり (220は除く)
足すと284になる。また、284=2×2×71で、その約数は1, 2, 4, 71, 142で、合計は220になる。

では、ここで問題。
3つ以上の数で構成される(nが3以上)社交鎖を見つけよ。
そのうち、「その鎖の中に登場する最小数」がもっとも小さい社交鎖を答えなさい。

ソース

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

class Program
{
    const int Jyougen = 80000; //社交鎖の中に登場する数の最大値

    static void Main()
    {
        Console.WriteLine("社交鎖の中に登場する数の最大値を{0}として検証します", Jyougen);

        var AnswerChainList = new List<int>();
        bool[] IsAppearedArr = new bool[Jyougen + 1]; //社交鎖で登場済の数を記憶

        for (int I = 1; I <= Jyougen; I++) {
            if (IsAppearedArr[I]) continue;

            var ChainList = DeriveChain(I);
            if (ChainList == null) continue;

            Console.Write("長さ{0}の社交鎖 ", ChainList.Count);
            ChainList.ForEach(X => Console.Write("{0},", X));
            Console.WriteLine("を発見");

            ChainList.ForEach(X => IsAppearedArr[X] = true);

            //社交鎖の長さが3以上の場合
            if (ChainList.Count >= 3) {
                if (AnswerChainList.Count == 0 || AnswerChainList.Min() > ChainList.Min()) {
                    AnswerChainList = ChainList;
                }
            }
        }
        Console.Write("解の社交鎖は");
        AnswerChainList.ForEach(X => Console.Write("{0},", X));
        Console.WriteLine();
    }

    //社交鎖を求める
    static List<int> DeriveChain(int pTarget)
    {
        var ValList = new List<int>() { pTarget };
        int CurrVal = pTarget;

        while (true) {
            int NextVal = DeriveYakusuuSum(CurrVal);

            //上限を超えた場合
            if (Jyougen < NextVal) return null;

            //出発点に戻った場合
            if (NextVal == pTarget) return ValList;

            //0に到着した場合
            if (NextVal == 0) return null;

            //ループした場合
            if (ValList.Contains(NextVal)) return null;

            ValList.Add(NextVal);
            CurrVal = NextVal;
        }
    }

    static int[] YakuduuSumArr = new int[Jyougen + 1];

    //真の約数の和を求める
    static int DeriveYakusuuSum(int pTarget)
    {
        if (pTarget == 1) return 0;
        if (YakuduuSumArr[pTarget] != 0) return YakuduuSumArr[pTarget];

        int WillReturn = 0;
        for (int I = 1; I * I <= pTarget; I++) {
            if (pTarget % I == 0) {
                WillReturn += I;
                if (I != 1) { //約数が1でない場合は、ペアの約数を求める
                    int PairVal = pTarget / I;
                    if (PairVal != I) WillReturn += PairVal;
                }
                if (Jyougen < WillReturn) return WillReturn;
            }
        }
        return YakuduuSumArr[pTarget] = WillReturn;
    }
}

実行結果

社交鎖の中に登場する数の最大値を80000として検証します
長さ1の社交鎖 6,を発見
長さ1の社交鎖 28,を発見
長さ2の社交鎖 220,284,を発見
長さ1の社交鎖 496,を発見
長さ2の社交鎖 1184,1210,を発見
長さ2の社交鎖 2620,2924,を発見
長さ2の社交鎖 5020,5564,を発見
長さ2の社交鎖 6232,6368,を発見
長さ1の社交鎖 8128,を発見
長さ2の社交鎖 10744,10856,を発見
長さ2の社交鎖 12285,14595,を発見
長さ5の社交鎖 12496,14288,15472,14536,14264,を発見
長さ2の社交鎖 17296,18416,を発見
長さ2の社交鎖 63020,76084,を発見
長さ2の社交鎖 66928,66992,を発見
長さ2の社交鎖 67095,71145,を発見
解の社交鎖は12496,14288,15472,14536,14264,

解説

社交鎖の中に登場する数の最大値を決めてから社交鎖を求めていき、
求まった解を検証してます。

Problem95 友愛鎖