Efficient algorithm for getting number of partitions of integer with distinct parts (Partition function Q)

I need to create function which will take one argument int and output int which represents the number of distinct parts of input integer's partition. Namely,

input:3 -> output: 1 -> {1, 2}
input:6 -> output: 3 -> {1, 2, 3}, {2, 4}, {1, 5}
...

Since I am looking only for distinct parts, something like this is not allowed:

4 -> {1, 1, 1, 1} or {1, 1, 2}

So far I have managed to come up with some algorithms which would find every possible combination, but they are pretty slow and effective only until n=100 or so. And since I only need number of combinations not the combinations themselves Partition Function Q should solve the problem. Does anybody know how to implement this efficiently?

More information about the problem: OEIS, Partition Function Q

EDIT:

To avoid any confusion, the DarrylG answer also includes the trivial (single) partition, but this does not affect the quality of it in any way.

EDIT 2: The jodag (accepted answer) does not include trivial partition.

Solution

I think a straightforward and efficient way to solve this is to explicitly compute the coefficient of the generating function from the Wolfram PartitionsQ link in the original post.

This is a pretty illustrative example of how to construct generating functions and how they can be used to count solutions. To start, we recognize that the problem may be posed as follows:

Let m_1 + m_2 + ... + m_{n-1} = n where m_j = 0 or m_j = j for all j.

Q(n) is the number of solutions of the equation.

We can find Q(n) by constructing the following polynomial (i.e. the generating function)

(1 + x)(1 + x^2)(1 + x^3)...(1 + x^(n-1))

The number of solutions is the number of ways the terms combine to make x^n, i.e. the coefficient of x^n after expanding the polynomial. Therefore, we can solve the problem by simply performing the polynomial multiplication.

def Q(n):
    # Represent polynomial as a list of coefficients from x^0 to x^n.
    # G_0 = 1
    G = [int(g_pow == 0) for g_pow in range(n + 1)]
    for k in range(1, n):
        # G_k = G_{k-1} * (1 + x^k)
        # This is equivalent to adding G shifted to the right by k to G
        # Ignore powers greater than n since we don't need them.
        G = [G[g_pow] if g_pow - k < 0 else G[g_pow] + G[g_pow - k] for g_pow in range(n + 1)]
    return G[n]

Timing (average of 1000 iterations)

import time
print("n    Time (sec)")
for n in [10, 50, 100, 200, 300, 500, 1000]:
    t0 = time.time()
    for i in range(1000):
        Q(n)
    elapsed = time.time() - t0
    print('%-5d%.08f'%(n, elapsed / 1000))

n    Time (sec)
10   0.00001000
50   0.00017500
100  0.00062900
200  0.00231200
300  0.00561900
500  0.01681900
1000 0.06701700