Skip to main content
コードに無駄があったので、修正しました。
ソース リンク
TOM
  • 1,582
  • 1
  • 14
  • 37

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)ary.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
  # ここまで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]

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
  # ここまで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]

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]
コードにコメントを追加。
ソース リンク
TOM
  • 1,582
  • 1
  • 14
  • 37

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
  # ここまで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]

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
  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]

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
  # ここまで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]
誤字修正を行いました。
ソース リンク
TOM
  • 1,582
  • 1
  • 14
  • 37

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
  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]

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
  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]

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
  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]
誤って編集したので、修正。
ソース リンク
TOM
  • 1,582
  • 1
  • 14
  • 37
読み込んでいます
余計な言葉の削除を行う。
ソース リンク
TOM
  • 1,582
  • 1
  • 14
  • 37
読み込んでいます
高速化についての質問を追加。
ソース リンク
TOM
  • 1,582
  • 1
  • 14
  • 37
読み込んでいます
コードの修正をしました。
ソース リンク
TOM
  • 1,582
  • 1
  • 14
  • 37
読み込んでいます
自分のコードの紹介をする。
ソース リンク
TOM
  • 1,582
  • 1
  • 14
  • 37
読み込んでいます
計算結果の正しさについて追記。
ソース リンク
TOM
  • 1,582
  • 1
  • 14
  • 37
読み込んでいます
少し形を整えました。
ソース リンク
TOM
  • 1,582
  • 1
  • 14
  • 37
読み込んでいます
ソース リンク
TOM
  • 1,582
  • 1
  • 14
  • 37
読み込んでいます