Project Euler 47,48,49問目

はじめに

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

47問目

それぞれ2つの異なる素因数を持つ連続する2つの数が最初に現れるのは:

14 = 2 × 7
15 = 3 × 5

それぞれ3つの異なる素因数を持つ連続する3つの数が最初に現れるのは:

644 = 22 × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19

最初に現れるそれぞれ4つの異なる素因数を持つ連続する4つの数を求めよ. その最初の数はいくつか?

private void button47_Click(object sender, EventArgs e)
        {
            var PrimeList = new List<int>(Eratosthenes(1000000));
            int j = 0;
            var Hash = new HashSet<int>();
            int Count = 0;
            int i = 647;
            while (true)
            {
                int Number = i;
                while (Number > PrimeList[j])
                {
                    if (Number % PrimeList[j] == 0)
                    {
                        Number /= PrimeList[j];
                        Hash.Add(PrimeList[j]);
                    }
                    else { j++; }
                }
                Hash.Add(Number);
                if (Hash.Count == 4)
                {
                    Count++;
                }
                else
                {
                    Count = 0;
                }
                if (Count == 4)
                {
                    label1.Text = "Answer = " + (i - 3);
                    break;
                }
                Hash.Clear();
                Hash.TrimExcess();
                i++;
                j = 0;
            }
        }

素数のリストを使って、647から1ずつ足していって割り切れた数が重複せず4つあるかを見て、それが4つ連続している数字を答えとしました。

48問目

11 + 22 + 33 + ... + 1010 = 10405071317 である.

では, $1^1 + 2^2 + 3^3 + ... + 1000^{1000}$ の最後の10桁を求めよ.

private void button48_Click(object sender, EventArgs e)
        {
            BigInteger Number = 1;
            BigInteger Sum = 0;
            for (BigInteger i = 1; i <= 1000; i++)
            {
                BigInteger j = i;
                for (int k = 0; k < j; k++)
                {
                    Number *= j;
                    Number %= 10000000000;
                }
                Sum += Number % 10000000000;
                Sum %= 10000000000;
                Number = 1;
            }
            label1.Text = "Answer = " + Sum;
        }

最後の10桁を求めるということなので、10桁になるように10桁で割った余りを足すようにしました。全て足したものを答えとしました。

49問目

公差3330の等差数列1487, 4817, 8147は次の2つの変わった性質を持つ.

(i)3つの項はそれぞれ素数である.
(ii)各項は他の項の置換で表される.
1, 2, 3桁の素数にはこのような性質を持った数列は存在しないが, 4桁の増加列にはもう1つ存在する.

それではこの数列の3つの項を連結した12桁の数を求めよ.

private void button49_Click(object sender, EventArgs e)
        {
            int[] Number = new int[3];
            for (int i = 1; Number[0] < 10000; i++)
            {
                Number[0] = 1000 + i;
                for (int diff = 3330; ; diff++)
                {
                    for (int j = 1; j < 3; j++)
                    {
                        Number[j] = Number[j - 1] + diff;
                    }
                    if (Number[2] > 10000) break;
                    if (Sosuu(Number[0]) == true && Sosuu(Number[1]) == true && Sosuu(Number[2]) == true)
                    {
                        var list1 = new List<char>(Number[0].ToString());
                        var list2 = new List<char>(Number[1].ToString());
                        var list3 = new List<char>(Number[2].ToString());
                        list1.Sort();
                        list2.Sort();
                        list3.Sort();
                        if (list1.SequenceEqual(list2) && list2.SequenceEqual(list3))
                        {
                            string Answer = Number[0].ToString() + Number[1].ToString() + Number[2].ToString();
                            label1.Text = "Answer = " + Answer;
                        }
                    }
                }
            }
        }

公差を1ずつ増やしながら、3つの項が10000より下であること、求めた3つの項が含んでいる数字が同じことを調べ、3つの項を連結したものを答えとしました。