最大積は

Question

私は本質的に以下に帰着問題が持っている因子。 ..、 _K）C、満足各n未満、：

1） _Iが最大とすべてのCの生成物。

2）すべての和がiでnと等しい。

これはMathOverflowの問題になるかもしれませんが、これを行うための非ブルートフォースアルゴリズムはありますか？

Answer 1

基本的には、nの任意のパーティションの最大公約数を探しています。この製品はランダウの機能として知られています（OEIS A000793参照）。これは、動的プログラミングを使用して計算できます（hereを参照）。