p(n)は、与えられた整数nの分割の総数を表すものとします。 さて、オイラーの分割恒等式とは、以下の恒等式をさします。 p(n | 和因子は奇数) = p(n | 和因子は相異なる) (http://ja.wikipedia.org/wiki/%E3%82%AA%E3%82%A4%E3%83%A9%E3%83%BC%E3%81%AE%E5%88%86%E5%89%B2%E6%81%92%E7%AD%89%E5%BC%8F) n = 1000 の場合について、以下のコードで 左辺( = p(n | 和因子は奇数) )を求めました。 n = 10 ** 3 ary = [] 1.step(n, 2){|i| ary << i} ps = Array.new(n + 1){0} ps[0] = 1 (1..n).each{|num| if ary.include?(num) (num..n).each{|i| ps[i] += ps[i - num] } end } p ps[n] 出力結果 8635565795744155161506 (この計算結果が正しいことは、以下のサイトで確認しました。 https://oeis.org/A069878) 右辺( = p(n | 和因子は相異なる) )を 何の工夫もなく以下のコードで求めたのですが、 もっと簡単で速く求める方法はないでしょうか? n = 10 ** 3 ps = Array.new(n + 1){0} ps[0] = 1 i = 0 while i < n j = [i * (i + 1) / 2, n].min i += 1 ary = ps.clone (0..j).each{|k| ary[k + i] += ps[k] if k + i <= n } ps = ary end p ps[n]