はじめに
C#を用いてProjectEulerに挑戦している人の記録です。VisualStudio2017で、1つのフォームアプリの中に問題番号のボタンを作成し、そのボタンをクリックすると結果をラベルに表示するという形式でやっています。
23問目
真の約数の和がその数よりも大きいものを過剰数と呼ぶ. 12は, 1 + 2 + 3 + 4 + 6 = 16 となるので, 最小の過剰数である. よって2つの過剰数の和で書ける最少の数は24である. 数学的な解析により, 28123より大きい任意の整数は2つの過剰数の和で書けることが知られている. 2つの過剰数の和で表せない最大の数がこの上限よりも小さいことは分かっているのだが, この上限を減らすことが出来ていない.
2つの過剰数の和で書き表せない正の整数の総和を求めよ.
private void button23_Click(object sender, EventArgs e)
{
var AbundantNumberList = new List<int>();
for (int i = 1; i <= 28123; i++)
{
int DivisorSum = 0;
for (int j = 1; j < i; j++)
{
if (i % j == 0)
{
DivisorSum += j;
}
}
if (DivisorSum > i)
{
AbundantNumberList.Add(i);
}
}
var MakedAbundantNumberHash = new HashSet<int>();
for (int i = 0; i < AbundantNumberList.Count; i++)
{
for (int j = 0; j < AbundantNumberList.Count; j++)
{
if (i <= j)
{
int MakedAbundantNumber = AbundantNumberList[i] + AbundantNumberList[j];
if (MakedAbundantNumber >= 28123)
{
break;
}
MakedAbundantNumberHash.Add(MakedAbundantNumber);
}
}
}
var NumberHash = new HashSet<int>();
for (int i = 1; i < 28123; i++)
{
NumberHash.Add(i);
}
NumberHash.SymmetricExceptWith(MakedAbundantNumberHash);
int Sum = NumberHash.Sum();
label1.Text = "Answer = " + Sum;
}
- 過剰数のリストを作る
- 過剰数の和が28123以下のハッシュセットを作る
- 28123までの値がはいったハッシュセットから、2のハッシュセットにある値を除外する
- 3のリストの和を計算
という形で行いました。もっといい方法がありそうです。
24問目
0,1,2,3,4,5,6,7,8,9からなる順列を辞書式に並べたときの100万番目はいくつか?
private void button24_Click(object sender, EventArgs e)
{
string[] NumberString = { "1", "2", "3", "4", "5", "6", "7", "8", "9", "0" };
var NumberList = new List<string>();
var stack = new Stack<string>();
stack.Push("2");
while (stack.Count > 0)
{
string Popped = stack.Pop();
if (Popped.Length == NumberString.Length)
{
NumberList.Add(Popped);
continue;
}
for (int i = 0; i < NumberString.Length; i++)
{
if (Popped.Contains(NumberString[i]) == false)
{
stack.Push(Popped + NumberString[i]);
}
}
}
NumberList.Sort();
label1.Text = "Answer = " + NumberList[274240 - 1];
}
スタックを使って、取り出した数字列にない数字を付加してスタックにいれ、10文字を取り出したらそれをリストに入れています。
この問題では、手計算をして計算量を減らしています。
- 順列のため、10の階乗=3628800がある一つの数字が先頭の個数
- 1000000-3628800*2=274240番目が1000000番目
- 0から順番に並べて、2が先頭の場合の274240番目が答えの数字
となります。
25問目
フィボナッチ数列の1000桁になる最初の項の番号を答えよ.
private void button25_Click(object sender, EventArgs e)
{
BigInteger Value = 0;
var NumberList = new List<BigInteger>();
NumberList.Add(1);
NumberList.Add(1);
for (int i = 1; ; i++)
{
Value = NumberList[i - 1] + NumberList[i];
NumberList.Add(Value);
string NumberString = Value.ToString();
if (NumberString.Length == 1000)
{
label1.Text = "Answer = " + (i + 2);
break;
}
}
}
フィボナッチ数列を計算してリストに入れながら、文字列に変換して長さが1000になったところで答えを出力しています。