Algorithm for the number of partitions of $n$ into distinct parts I am looking for an algorithm to find the number of ways of writing $n$ as a sum of positive integers without regard to order with the constraint that all integers in a given partition are distinct. This is described in here and OEIS A000009.  I've found an implementation in LISP for Maxima, but I don't know LISP and couldn't really figure out the algorithm.
 A: Let $N(k,n)$ be the algorithm computing the numb rod ways of writing $n$ as the sum of integers greater than $k$. $N(k,n)$ is defined inductively as follow:


*

*$N(k,n)=0$ if $k>n$;

*$N(k,n)=1$ if $k=n$;

*$N(k,n)=N(k+1,n)+N(k+1,n-k)$


Is that helpful?
A: This is called the partition number $Q(n)$. There is a recurrence relation for this given here (see equation 11), namely
$$Q(n) = s(n) + 2\sum_{i=1}^\sqrt{n}(-1)^{k+1}Q(n-k^2)$$
where 
$$s(n) = \begin{cases}
    (-1)^j,& \text{if } n= j(3j \pm 1)/2\\
    0,              & \text{otherwise}
\end{cases}$$
You can use this (along with a base case) to iteratively populate an array with the values of $Q(n)$.
A: I made the following descent algorithm (natural is typedef as unsigned long long) for c++17.
Yo must include map and cmath headers. The cache maps are for speed up nested calculus with big integers. Hope this helps.
natural distinct_parts_partition(const natural& n)
{
    typedef std::map<natural, natural> natural_map;
    std::map<natural,natural_map> cache_map;

    std::function<natural (natural)> border = [](natural value)
    {
        /**
        The sum 1+...+n yields n*(n+1)/2 so the n value of the
        range that can yield a value s must satisfy
        n*(n+1) >= 2*s 
        That's, the inecuation n^2+n-2s >= 0 fulfills.
        Hence,the minimal n is done by
        n = ceil((-1+sqrt(1+8s))/2)
        That's the result of this method
        **/
        return natural(ceil((-1.0+sqrt(1.0+8.0*double(value)))/2.0));
    };

    std::function<natural (natural, natural)> compute = [&](natural s, natural top)
    {
        if (top*(top+1)<2*s)
        {
            return natural(0);
        }
        if ( s < 3 )
        {
            return natural(1);
        }
        auto cache_entry_root = cache_map.find(s);
        if ( cache_entry_root != cache_map.end() )
        {
            auto& cache_child = cache_entry_root->second;
            auto cache_entry_child = cache_child.find( top );
            if ( cache_entry_child != cache_child.end() )
            {
                return cache_entry_child->second;
            }
        }
        natural result = 0;
        /**
        while top-i > s/2, we add compute(s-top+i,s-top+i).
        if top-i = s/2 we add compute(s/2,s/2) - 1 (avoid n+n counting).
        While (top-i)*(top-i+1) >= 2*s, we add again compute(s-top+i,top-i-1).
        **/
        natural key = top;
        while ( 2*key > s )
        {
            result += compute(s-key, s-key);
            --key;
        }
        if( 2*key == s )
        {
            result += compute(key, key) - 1;
            --key;
        }
        natural intro = border(s);
        while ( key >= intro )
        {
            result += compute(s-key, key-1);
            --key;
        }
        if( cache_entry_root == cache_map.end() )
        {
            natural_map entry;
            entry[top] = result;
            cache_map[s] = entry;
        }
        else
        {
            auto& entry = cache_entry_root->second;
            entry[top] = result;
        }
        return result;
    };
    return compute(n,n);        
}

