Problem23 2つの過剰数の和で書き表せない正の整数の総和

問題

完全数とは, その数の真の約数の和がそれ自身と一致する数のことである.
たとえば, 28の真の約数の和は,1+2+4+7+14=28であるので, 28は完全数である.

真の約数の和がその数よりも少ないものを不足数といい,
真の約数の和がその数よりも大きいものを過剰数と呼ぶ.

12は, 1+2+3+4+6=16となるので, 最小の過剰数である.
よって2つの過剰数の和で書ける最小の数は24である.

数学的な解析により, 28123より大きい任意の整数は2つの過剰数の和で書けることが知られている.
2つの過剰数の和で表せない最大の数がこの上限よりも小さいことは分かっているのだが,
この上限を減らすことが出来ていない.

2つの過剰数の和で書き表せない正の整数の総和を求めよ.

ソース

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

class Program
{
    static void Main()
    {
        var KouhoList = new List<int>();
        for (int I = 1; I <= 28123; I++) {
            int YakusuuSum = DeriveYakusuuSum(I);
            if (YakusuuSum > I) KouhoList.Add(I);
        }

        var IsExistArr = new bool[28123 + 1];

        for (int I = 0; I <= KouhoList.Count - 1; I++) {
            for (int J = I; J <= KouhoList.Count - 1; J++) {
                int wkInd = KouhoList[I] + KouhoList[J];
                if (wkInd <= IsExistArr.GetUpperBound(0))
                    IsExistArr[wkInd] = true;
            }
        }

        int SumVal = 0;
        for (int I = 1; I <= IsExistArr.GetUpperBound(0); I++) {
            if (IsExistArr[I] == false) SumVal += I;
        }
        Console.WriteLine("合計={0}", SumVal);
    }

    //真の約数の和を求める
    static int DeriveYakusuuSum(int pTarget)
    {
        var YakusuuSet = new HashSet<int>();

        for (int I = 1; I * I <= pTarget; I++) {
            if (pTarget % I == 0) {
                YakusuuSet.Add(I);
                YakusuuSet.Add(pTarget / I);
            }
        }

        int WillReturn = 0;
        foreach (int EachInt in YakusuuSet) {
            if (EachInt != pTarget)
                WillReturn += EachInt;
        }
        return WillReturn;
    }
}

実行結果

合計=4179871

解説

HashSetで真の約数を管理してます。