Herd Sums(6)

最短コードが狙えるアルゴリズム(下)

超単純な探索方法を発見したものの、巨大なインプットに対してこの方法が必ず成り立つのだろうか。
・・・よーわからんなぁ(;´д｀)
というわけで、ちょっとロベールさんに聞いてみたところ、ちょちょいと証明してくれました。さすが！

以下、ロベールさんの説明

(a-1)+a+(a+1)
のように、ある数を中心として分布するには、奇数個の項が必要。
(a-1)+a+(a+1)+(a+2)
のように、ある対 a+(a+1) を中心として分布する場合、その対の合計は奇数になる。このように、級数を作るためには、ここで鍵となる奇数の倍数であることが必要になる。

n = o v　（o は奇数で、v は正の整数）

1) v が偶数の場合
v を中心とした o 個の級数と、足して o になる v 個の対からなる級数が作れる可能性がある。

前者が作れる場合、級数の初項 ≧ 1 より、
　v - (o - 1) / 2 ≧ 1
である必要がある。

後者が作れる場合、級数の初項 ≧ 1 より、
　(o - 1) / 2 - (v - 1) ≧ 1
である必要がある。
すなわち
　0 ≧ v - (o - 1) / 2
である。

これら２つの条件は同時に満たされることはなく、
またこれら２つの条件に入らない場合は存在しないので、
必ず一種類の級数のみが作れることになる。

2) v が奇数の場合
v と o を逆にした場合も考えられるが、
同様に考えればこの逆にした方も一種類の級数しか作れない。
従って、両方合わせて二種類の級数のみが作れることになる。

1), 2) より、問題の級数の数は、奇数の約数の数に等しくなる。

なるほど、たまたま通ったのではなく、この方法は一般的に正しいと言えるのか！！よっしゃ、これで最短コードが完成じゃ！！！