python - Python と数論: q(n) (n を個別の部分に分割する数) の生成関数を作成するにはどうすればよいですか?

Question

https://en.wikipedia.org/wiki/Partition_%28number_theory%29#Restricted_pa​​rtitionsから、整数 p(n) の分割数は

Python では次のように記述できます。

def partitions(n, I=1):
    yield(n,)
    for i in range(I, n//2 + 1):
        for p in partitions(n-i, i):
            yield (i,) + p

私の質問は次のとおりです。これを変更して、個別の部分を含むパーティションの数であるq(n)を返すにはどうすればよいですか?

すなわち;

p(3)=2、 3=2+1 3=1+1+1 (1,1,1)区別されないためです。

しかし、異なる要素q(3)=1のみが含まれているため です。3=2+1

の生成関数はq(n)、

n から無限大までの積を返す Python の良い積関数が見つかりません。

Answer 1

実際の整数を使用して n から無限大までの積を計算できるコンピュータはありません。

最も効率的な解決策は次のとおりだと思います

import functools

@functools.lru_cache(maxsize=None)  # save previous results
def unique_partitions(n, I=1):
    yield (n,)
    for i in range(I, n//2 + 1):
        for p in unique_partitions(n - i, i):
            if i not in p:  # eliminate non-unique results
                yield (i,) + p

その後、それらを次のように数えることができます

def q(n):
    count = 0
    for _ in unique_partitions(n):
        count += 1
    return count