【Project Euler】Problem 76: 整数の分割

---

• 本記事は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）