Y箱

ここのところ続いている、分割数の問題です。

前までの漸化式で解こうとしたら、時間がかかってだめ。
Wikipediaを見なおしてみると、別の漸化式があったのでこっちでやってみたら、まあ、なんとか。







式はこれ。 オイラーの五角数定理だそうな。

p(k) = p(k − 1) + p(k − 2) − p(k − 5) − p(k − 7) + p(k − 12) + p(k − 15) − p(k − 22) − ...

ここで出てくる数列 ( 1 2 5 7 12 15 22 ) は、負の数を含めた五角数で、ほんとはマイナス無限大から無限大までの整数に対する五角数の並び(…15 7 2  1 5 12 22…)を 1 で 折り返したもの。
また、p(0) = 1、負の数の場合を0として計算すると答えが出るらしい。




・ pentagonal
  五角数を計算します。

・  partition-num
  p(n) を計算します。
  ->> のところは、 1 -1 2 -2 3 -3 4 -4  を作って、 それぞれの五角数を求めて、kより大きいものを省いています。
  それを p(k-?) の式にあてはめて、計算してます。

・ pe78
  p(n) を1から順に計算して、limitで割って余りが無くなる最初のものを計算します。