Mae向きなブログ

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

Problem 78

Ruby Euler

Project EulerのProblem 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