Skip to content
{{ message }}

Instantly share code, notes, and snippets.

# ha0ye/partition function calculator.R

Last active Mar 29, 2017
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 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, so check for that case here and note Q = 1 else temp <- temp + 2 * (-1)^((k+1) %% 2) * Q_table[n - k^2] } Q_table[n] <- temp }
to join this conversation on GitHub. Already have an account? Sign in to comment