9576


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 | 和因子は奇数) ）を求めました。

[code]

    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]
    
[/code]

出力結果  
8635565795744155161506  
（この計算結果が正しいことは、以下のサイトで確認しました。  
<https://oeis.org/A069878>）

右辺（ = p(n | 和因子は相異なる) ）を  
何の工夫もなく以下のコードで求めたのですが、  
もっと速く求める方法はないのでしょうか？

[code]

    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]
    
[/code]


CC BY-SA 3.0
2015-04-25T13:47:56.013
9548
2015-12-28T13:56:18.357
2015-12-28T13:56:18.357
5363
5363
question
ruby アルゴリズム
オイラーの分割恒等式をプログラミングで確認するには？


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

[code]

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

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

[code]

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

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

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

[code]

    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;
    }
    
[/code]


CC BY-SA 3.0
2015-04-25T15:43:43.357
9551
2015-04-25T15:43:43.357
5750
9548
answer


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

[code]

    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]
    
[/code]

（コメント）  
例えば、10の分割を考えるとき  
10、  
9 + 1、  
8 + 2、  
…  
とするように、大きいものから探してみました。


CC BY-SA 3.0
2015-04-26T19:41:20.493
9576
2015-04-26T20:39:15.070
2015-04-26T20:39:15.070
5363
5363
9548
answer