Python and Number Theory: How can we create the generating function for q(n) (the number of partitions of n into distinct parts)?

Question

From https://en.wikipedia.org/wiki/Partition_%28number_theory%29#Restricted_partitions, we know that the number of partitions of an integer p(n) is given by

Can be written in python as:

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

My question is: How can I modify this to return q(n), the number of partitions containing distinct parts?

i.e.;

p(3)=2, because 3=2+1 3=1+1+1 (1,1,1) are not distinct.

but q(3)=1, because only 3=2+1 contains distinct elements.

The generating function of q(n) is given by

I can't find a good product function in python that returns a product from n to infinity.

Answer 1

Рус

Добрый день, я не могу оставить комментарий под ответом FHTMitchell, поэтому оставляю его отдельно. В моём случае строка

@functools.lru_cache(maxsize=None)  # save previous results

приводит к ошибкам в расчётах. Также прилагаю свой вариант функции для расчёта всех значений от 1 до N.

En (google translate)

Good afternoon, I can not leave a comment under the answer FHTMitchell, so I leave my comment separately. In my case, the string

@ functools.lru_cache (maxsize = None) # save previous results

leads to errors in calculations. I also attach my version of the function to calculate all values ​​from 1 to N.

Число   Эталон  Расчёт   Ошибка 
1       1       1               
2       1       1               
3       2       2               
4       2       2               
5       3       3               
6       4       3        Ошибка 
7       5       4        Ошибка 
8       6       4        Ошибка 
9       8       5        Ошибка 
10      10      5        Ошибка 
11      12      6        Ошибка 
12      15      6        Ошибка 
13      18      7        Ошибка 
14      22      7        Ошибка 
15      27      8        Ошибка 
16      32      8        Ошибка 
17      38      9        Ошибка 
18      46      9        Ошибка 
19      54      10       Ошибка 
20      64      10       Ошибка 
21      76      11       Ошибка 
22      89      11       Ошибка 
23      104     12       Ошибка 
24      122     12       Ошибка 
25      142     13       Ошибка

Мой вариант функции:
My variant of the function:

def partit(N=10):
    part = {}

    for i in range(1, N + 1):
        part[i] = [(j, i - j) for j in range(1, i + 1) if j < i - j]

    for i in range(1, N + 1):
        temp = []
        for up, down in part[i]:
            p2 = [(up, (u, d)) for u, d in part[down] if u > up]
            temp.extend(p2)
        part[i].extend(temp)

    return {i:len(part[i])+1 for i in part}

Может кому-то пригодится ряд из 100 первых чисел:

Someone can use a series of 100 first numbers:

1 1 2 2 3 4 5 6 8 10 12 15 18 22 27 32 38 46 54 64 76 89 104 122 142 165 192 222 256 296 340 390 448 512 585 668 760 864 982 1113 1260 1426 1610 1816 2048 2304 2590 2910 3264 3658 4097 4582 5120 5718 6378 7108 7917 8808 9792 10880 12076 13394 14848 16444 18200 20132 22250 24576 27130 29927 32992 36352 40026 44046 48446 53250 58499 64234 70488 77312 84756 92864 101698 111322 121792 133184 145578 159046 173682 189586 206848 225585 245920 267968 291874 317788 345856 376256 409174 444793

Answer 2

Well no computer can calculate products from n to infinity using actual integers.

I think the most efficient solution is as follows

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

You can then count them as

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