- 本記事はProjectEulerの「100番以下の問題の説明は記載可能」という規定に基づいて回答のヒントが書かれていますので、自分である程度考えてみてから読まれることをお勧めします。
問題 76. 整数の分割
原文 Problem 76: Counting summations
問題の要約：100を自然数の和で何通りの組み合わせで表せるかを求めよ
分割数の漸化式
これは有名な「自然数の分割（Wikipedia）」の問題ですね。たぶんこれだけで本が書けるくらい多くの話題がありそうですが、こちらの「分割数の意味と性質・ヤング図形の活躍」が割と簡潔にまとまっているかなと思います。ここで以下の漸化式が出ています。
p_k(n)=p_k(n−k)+p_{k−1}(n−1)
再帰関数での実装
これをもとにして書いたのがこちら、再帰関数で繰り返しが多いのでlru_cacheを使っています。
from functools import lru_cache
@lru_cache(maxsize=None)
def npart(n, k):
if n == 0 or k==1: return 1
ret = npart(n, k-1)
if n >= k:
ret += npart(n-k, k)
return ret
n = 100
print("Answer: {npart(n,n)-1}")
配列を使った実装
再帰関数を使わずに配列を使って実装したのがこちら。かなりシンプルになってます。
def npart(n):
p = [1]+[0]*n
for i in range(1, n+1):
for j in range(i, n+1):
p[j] += p[j-i]
return p[n]
print(f"Answer: {npart(100)-1}")
sympyの関数（partitions, npartitions）
これだけ有名な問題なのでさすがにsympyにありますね。まずは分割の数をすべてリストしてくれるpartitions
from sympy.utilities.iterables import partitions
n = 4
print(list(partitions(n)))
# [{4: 1}, {3: 1, 1: 1}, {2: 2}, {2: 1, 1: 2}, {1: 4}]
そしてまさに分割数を返す関数npartitions。あっけなく答えが求まります。
from sympy.ntheory import npartitions
print(f"Answer: {npartitions(100)-1}")
（開発環境：Google Colab）