なんでそうなのかをコンピュータによる実証以外に証明する事ができないので、ドラクエで言うと、まだ冒険の書を作ったところ。
いや、冒険の書すら作れていないのか。
nまでの整数を二つの組に分けて合計した結果が同じ時のnについて見つけた法則 – NAL-6295の舌先三寸
最近、続けている話題ですが、とりあえず見つけた法則が正しいのかどうかを実証するために法則を見つける前のコードをPCで実行させてみたら、さすがに死ぬほど時間がかかって800000に辿りつくまでですら一晩かかったので、バイナリサーチで書き直してみた。
配列なら、Array.BinarySearchがあるのだけれども・・・。
バイナリサーチにしたら、intの幅に関しては、１時間２０分くらいで、戻ってくるようになった。
アルゴリズム一つでぜんぜん違うという事を改めて（今更ながら）実感。
public void nまでの整数を二つの組に分けて合計した結果が同じだった数字リスト実証()
{
Func<int, bool> 奇数が奇数個ある = x => ((x / 2) + (x % 2)) % 2 != 0;
Func<long, long, long> xからyまでの計 = (x, y) => ((x + y) * ((y - x + 1) / 2)) + (((y + x) / 2) * ((y - x + 1) % 2));
Func<int, long,long,long, bool> nまでの数字の合計の半分とnを二つの組にした合計が同じものがある = null;
nまでの数字の合計の半分とnを二つの組にした合計が同じものがある = (n, 総和の半分, 始点, 終点) =>
{
long 探索点 = (終点 + 始点) / 2;
long 総和 = xからyまでの計(探索点, (long)n);
if (総和 == 総和の半分)
{
return true;
}
if (始点 == 終点)
{
return false;
}
if (総和 > 総和の半分)
{
始点 = 探索点;
}
else
{
終点 = 探索点;
}
if (始点 + 1 == 終点)
{
if (総和 > 総和の半分)
{
始点++;
}
else
{
終点--;
}
}
return nまでの数字の合計の半分とnを二つの組にした合計が同じものがある(n, 総和の半分, 始点, 終点);
};
var 該当するnのリスト = Enumerable
.Range(2, int.MaxValue - 2)
.Where(n => !奇数が奇数個ある(n) && nまでの数字の合計の半分とnを二つの組にした合計が同じものがある(n, xからyまでの計(1, n) / 2, 1, n))
.Select(n => n);
foreach (var n in 該当するnのリスト)
{
Console.WriteLine(n);
}
}
