Mae向きなブログ

Mae向きな情報発信を続けていきたいと思います。

Problem 78

Project EulerProblem 78(日本語)です。
6/5(火)のProblem 76のような解き方だと時間がかかりすぎて解くことができませんでした。Wikipediaの分割数には、以下のような漸化式も紹介されています。以前、Problem 44,Problem 45で出てきた五角数が分割数を解く漸化式に登場するとは驚きでした。

p(k)=p(k-1)+p(k-2)-p(k-5)-p(k-7)+p(k-12)+p(k-15)-p(k-22)-...
ここでp(0)=1および負の整数kに対してp(k)=0とし、和は\frac{1}{2}n(3n-1) の形(ただしnは正または負の整数全体を走る)の一般五角数全体にわたってとるものとする(順にn = 1, -1, 2, -2, 3, -3, 4, -4 ...,とすると、値として1, 2, 5, 7, 12, 15, 22, 26, 35, 40, 51, ...が得られる)。和における符号は交互に+, +, -, -, +, +, ...と続く。

078.rb