Entries from 2018-10-06 to 1 day

Find the nth partition number mod p in O(n log n)

This algorithm comes from a study of subset sum [1]. exp, log, recip are described in [2]. The generating function of partition number is \[ (1+x+x^2+\cdots)(1+x^2+x^4+\cdots)(1+x^3+x^6+\cdots)\cdots. \]The logarithm of this function is\[ …