2

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
ary.each{|num|
  (num..n).each{|i|
    ps[i] += ps[i - num]
  }
}
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
  # ここまでiが最大の因子
  i += 1
  j = [(i - 1) * i / 2, n - i].min
  ary = ps.clone
  (0..j).each{|k|
    ary[k + i] += ps[k]
  }
  ps = ary
end
p ps[n]

2 件の回答 2

3

mの和因子が相異なる分割で、最大の因子がu以下であるものの総数を返す関数f(m,u)を考えれば

p(n | 和因子は相異なる) = f(n,n)

ですが、この関数は最大和因子をiと仮定すると

f(m,u) = Σ f(m-i, i-1) ※i∈[1,u]

となります。なので再帰でシンプルに表現できます。

C#で書いた場合はこんな感じです。1000でやると無茶苦茶遅いと思いますが。

private static long Count(int sum, int partitionUpperbound)
{
    var u = Math.Min(sum, partitionUpperbound);

    long s = 0;
    for (var i = u; i > 0; i--)
    {
        var rem = sum - i;
        if (rem == 0)
        {
            s += 1;
        }
        else if (i > 1)
        {
            s += Count(rem, i - 1);
        }
    }

    return s;
}
0
1

質問のコードよりこちらのコードの方が少し速い。

n = 10 ** 4

ps = Array.new(n + 1){0}
ps[0] = 1
i = n + 1
while i > 1
  # ここまでiが最小の因子
  i -= 1
  j = [(n + i) * (n - i + 1) / 2, n - i].min
  ary = ps.clone
  (0..j).each{|k|
    ary[k + i] += ps[k]
  }
  ps = ary
end
p ps[n]

(コメント)
例えば、10の分割を考えるとき
10、
9 + 1、
8 + 2、

とするように、大きいものから探してみました。

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。