Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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.
# 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
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.