Project Euler 44,45,46問目

はじめに

C#を用いてProjectEulerに挑戦している人の記録です。VisualStudio2017で、1つのフォームアプリの中に問題番号のボタンを作成し、そのボタンをクリックすると結果をラベルに表示するという形式でやっています。

44問目

五角数は $P_n = \frac{n(3n-1)}{2}$ で生成される. 最初の10項は
$1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...$
である.

$P_4 + P_7 = 22 + 70 = 92 = P_8$ である. しかし差 $70 - 22 = 48$ は五角数ではない.

五角数のペア $P_j$ と $P_k$ について, 差と和が五角数になるものを考える. 差を $D = |P_k - P_j|$ と書く. 差 D の最小値を求めよ.

private void button44_Click(object sender, EventArgs e)
        {
            var PentaList = new List<int>();
            for (int i = 1; i < 10000; i++)
            {
                PentaList.Add(i * ((3 * i) - 1) / 2);
            }
            for (int i = 0; i < 9980; i++)
            {
                for (int j = 0; j < 9980; j++)
                {
                    if (i < j)
                    {
                        if (PentaList.Contains(PentaList[i] + PentaList[j]) && PentaList.Contains(Math.Abs(PentaList[i] - PentaList[j])))
                        {
                            textBox1.AppendText(PentaList[i] + " " + PentaList[j] + " ");
                            label1.Text = "Answer = " + Math.Abs(PentaList[i] - PentaList[j]);
                            goto end;
                        }
                    }
                }
            }
        end:;
        }

五角数を10000項目までリストに入れ、和と差がどちらもリストに含まれている場合を答えとしました。差の最小値なので、下から見ていって一番最初に見つかったものが最小値という考えです。

45問目

三角数, 五角数, 六角数は以下のように生成される
三角数 $T_n=\frac{n(n+1)}{2}$ 1, 3, 6, 10, 15, ...
五角数 $P_n=\frac{n(3n-1)}{2}$ 1, 5, 12, 22, 35, ...
六角数 $H_n=n(2n-1)$ 1, 6, 15, 28, 45, ...

$T_{285} = P_{165} = H_{143} = 40755$であることが分かる.

次の三角数かつ五角数かつ六角数な数を求めよ.

public static long CalcKakusuu(long Kakusuu, long N)
        {
            if (Kakusuu == 3) return N * (N + 1) / 2;
            if (Kakusuu == 5) return N * (3 * N - 1) / 2;
            return N * (2 * N - 1);
        }

        private void button45_Click(object sender, EventArgs e)
        {
            long TriangleIndex = 2;
            long PentagonalIndex = 2;
            long HexagonalIndex = 2;

            long Triangle = CalcKakusuu(3, TriangleIndex);
            long Pentagonal = CalcKakusuu(5, PentagonalIndex);
            long Hexagonal = CalcKakusuu(6, HexagonalIndex);

            int count = 0;
            while (true)
            {
                if (Triangle == Pentagonal && Pentagonal == Hexagonal)
                {
                    count++;
                    if (count == 2) break;
                }
                if (Math.Min(Math.Min(Triangle, Pentagonal), Hexagonal) == Triangle)
                {
                    Triangle = CalcKakusuu(3, ++TriangleIndex);
                    continue;
                }
                if (Math.Min(Math.Min(Triangle, Pentagonal), Hexagonal) == Pentagonal)
                {
                    Pentagonal = CalcKakusuu(5, ++PentagonalIndex);
                    continue;
                }
                if (Math.Min(Math.Min(Triangle, Pentagonal), Hexagonal) == Hexagonal)
                {
                    Hexagonal = CalcKakusuu(6, ++HexagonalIndex);
                    continue;
                }
            }
            label1.Text = "answer = " + Triangle;
        }

三角数、五角数、六角数の3つを比べて、等しいかどうか確認した後、一番小さい数のインデックスを進めた
数を代入します。2番目の3つが等しい数を見つけるため、カウントが2になったら終了して答えとしています。

46問目

Christian Goldbachは全ての奇合成数は平方数の2倍と素数の和で表せると予想した.

$9 = 7 + 2×1^2$
$15 = 7 + 2×2^2$
$21 = 3 + 2×3^2$
$25 = 7 + 2×3^2 $
$27 = 19 + 2×2^2$
$33 = 31 + 2×1^2$

後に, この予想は誤りであることが分かった.

平方数の2倍と素数の和で表せない最小の奇合成数はいくつか?

private void button46_Click(object sender, EventArgs e)
        {
            var list = new List<int>(Eratosthenes(10000));
            var IntegerList = new List<int>();
            for (int i = 9; i < 10000; i += 2)
            {
                IntegerList.Add(i);
            }
            for (int i = 0; i < list.Count; i++)
            {
                for (int j = 0; j < 10000; j++)
                {
                    if (IntegerList.Contains(list[i] + 2 * j * j))
                    {
                        IntegerList.Remove(list[i] + 2 * j * j);
                    }
                }
            }
            label1.Text = "Answer = " + IntegerList.Min();
        }

合成数とは、素数でない数のことです。素数のリストを作り、奇数のリストを作った後、奇数のリストから素数を取り除いて残った数の一番小さい数を答えとしました。