Compute the Partition Function Q: the number of ways of writing n as a sum of positive integers, disregarding order, but with the constraint that all integers are distinct.

partition function calculator.R

# For more info, see http://mathworld.wolfram.com/PartitionFunctionQ.html
# This uses the 2nd recurrence relation defined therein.

max_n <- 1000

# helper function
s <- integer(length = max_n)
for(j in 1:sqrt((2*max_n+1)/3))
{
    n <- j * (3 * j + 1) / 2
    if(n <= length(s))
        s[n] <- (-1)^(j %% 2)
    n <- j * (3 * j - 1) / 2
    if(n <= length(s))
        s[n] <- (-1)^(j %% 2)
}

# table of results
Q_table <- numeric(max_n) # use numeric because of integer overflow for large n
Q_table[1] <- 1

for(n in 2:max_n)
{
    temp <- s[n]
    for(k in 1:sqrt(n))
    {
        if(n == k^2)
            temp <- temp + 2 * (-1)^((k+1) %% 2) # we don't have Q[0], so check for that case here and note Q[0] = 1
        else
            temp <- temp + 2 * (-1)^((k+1) %% 2) * Q_table[n - k^2]
    }
    Q_table[n] <- temp
}