Project Euler 56,57,58問目

#はじめに
C#を用いてProjectEulerに挑戦している人の記録です。VisualStudio2017で、1つのフォームアプリの中に問題番号のボタンを作成し、そのボタンをクリックすると結果をラベルに表示するという形式でやっています。
#56問目
Googol $(10^{100})$は非常に大きな数である: 1の後に0が100個続く. $100^{100}$は想像を絶する. 1の後に0が200回続く. その大きさにも関わらず, 両者とも数字和 ( 桁の和 ) は1である.

$a, b < 100$ について自然数 $a^b $を考える. 数字和の最大値を答えよ.

```CSharp
private void button56_Click(object sender, EventArgs e)
        {
            int MaxNumberSum = 0;

            for (int a = 1; a < 100; a++)
            {
                BigInteger Value = a;
                for (int b = 1; b < 100; b++)
                {
                    Value *= a;
                    var DigitNumberCharList = new List<char>(Value.ToString());
                    var DigitNumberIntList = new List<int>();
                    for (int i = 0; i < DigitNumberCharList.Count; i++)
                    {
                        DigitNumberIntList.Add(DigitNumberCharList[i] - '0');
                    }
                    int DigitNumberSum = DigitNumberIntList.Sum();
                    if (MaxNumberSum < DigitNumberSum)
                    {
                        MaxNumberSum = DigitNumberSum;
                    }
                }
            }
            label1.Text = "Answer=" + MaxNumberSum;
        }
```

$a,b<100, a^b$のループの中で、BigInteger型の累乗した値をchar型に変換して、それをint型に変換して数字和を出しています。その最大値を答えとしました。
#57問目
2の平方根は無限に続く連分数で表すことができる.

$√ 2 = 1 + \frac{1}{(2 + \frac{1}{(2 + \frac{1}{(2 + ... }}} = 1.414213...$
最初の4回の繰り返しを展開すると以下が得られる.

$1 + \frac{1}{2} = \frac{3}{2} = 1.5$
$1 + \frac{1}{2 + \frac{1}{2}} = \frac{7}{5} = 1.4$
$1 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2}}} = \frac{17}{12} = 1.41666...$
$1 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2}} }}= \frac{41}{29} = 1.41379...$

次の3つの項は$\dfrac{99}{70}, \dfrac{239}{169}, \dfrac{577}{408}$である. 第8項は$\dfrac{1393}{985}$である. これは分子の桁数が分母の桁数を超える最初の例である.

最初の1000項を考えたとき, 分子の桁数が分母の桁数を超える項はいくつあるか?

```CSharp
private void button57_Click(object sender, EventArgs e)
        {
            int Count = 0;
            var NumerList = new List<BigInteger>();
            var DenomList = new List<BigInteger>();
            NumerList.Add(3);
            NumerList.Add(7);
            DenomList.Add(2);
            DenomList.Add(5);
            for (int i = 2; i <= 1000; i++)
            {
                DenomList.Add(DenomList[i - 1] + NumerList[i - 1]);
                NumerList.Add(DenomList[i - 1] + DenomList[i]);
                if (NumerList[i].ToString().Length > DenomList[i].ToString().Length)
                {
                    Count++;
                    textBox1.AppendText(" " + NumerList[i] + "," + DenomList[i]);
                }
            }
            label1.Text = "Answer=" + Count;
        }
```
数列に規則性がありました。n項めは分母はn-1の分子と分母の和、分子はnの分母にn-1の分母を足すという規則性です。それを使って、1000項目までを計算し、分子の桁数が分母の桁数を超える回数をカウントして答えとしました。

#58問目
1から始めて, 以下のように反時計回りに数字を並べていくと, 辺の長さが7の渦巻きが形成される.

**37**	36	35	34	33	32	**31**
38	**17**	16	15	14	**13**	30
39	18	 **5**	 4	 **3**	12	**29**
40	19	 6	 1	 2	11	28
41	20	 **7**	 8	 9	10	27
42	21	22	**23	24	25	26
**43**	44	45	46	47	48	49
面白いことに, 奇平方数が右下の対角線上に出現する. もっと面白いことには, 対角線上の13個の数字のうち, 8個が素数である. ここで割合は8/13 ≈ 62%である.

渦巻きに新しい層を付け加えよう. すると辺の長さが9の渦巻きが出来る. 以下, この操作を繰り返していく. 対角線上の素数の割合が10%未満に落ちる最初の辺の長さを求めよ.

```CSharp
private void button58_Click(object sender, EventArgs e)
        {
            int Value = 1;
            double PrimeCount = 0;
            int Answer = 0;
            int SideLength = 0;
            var List = new List<double>();
            for (int i = 1; ; i++)
            {
                for (int j = 0; j < 4; j++)
                {
                    Value += i * 2;
                    if (Sosuu(Value) == true)
                    {
                        PrimeCount++;
                    }
                    if (j == 2)
                    {
                        SideLength = Value - (Value - i * 2) + 1;
                    }
                }
                double Percentage = PrimeCount / (1 + (i * 4));
                List.Add(Percentage);
                if (Percentage < 0.1)
                {
                    Answer = SideLength;
                    break;
                }
            }
            label1.Text = "Answer = " + SideLength;
        }
```
対角線の数字だけを出して考えています。対角線の数字は2ずつ増えていけばいいので、2ずつ増やし、横の長さも計算して、素数の割合を計算して0.1以下の時の横の長さを答えとしました。
#感想
56問目はそのまま実装しましたが、57、58問目は少しアルゴリズムを簡単にできたのではないかと思います。なるべく計算量を減らすように作っていきたいです。