Timeline for unique integer partitions
Current License: CC BY-SA 2.5
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 10, 2010 at 5:22 | comment | added | falagar | For those $n$n and $k$ I can suggest the following. Start with the approach suggested by Qiaochu Yuan. Take polynomial $f(x) = (1-x)(1-x^2)\cdots(1-x^k)$ and calculate it as $f(x) = f_0 + f_1 x + \cdots + f_{k(k+1)/2} x^{k(k+1)/2}$. Now you need coefficient with $x^n$ in $1/f(x)$. To calculate it apply Fast Fourier Transform to inverse polynomial $f(x)$. This works in $O(n \log n)$ basic operations (multiplications and additions). So the overall complexity is $O(n \log n)$ | |
| Jul 10, 2010 at 1:50 | comment | added | B Rivera | +1 thanks for the answer. but if, say, $n = 10^{7}$ and $k = 2000$, i fear that i'd be sitting around for quite a while for the recursion to finish or i might reach the recursion depth of my programming language. do you know of any asymptotic results? maybe along the lines of hardy-ramanujan? | |
| Jul 9, 2010 at 9:29 | history | answered | falagar | CC BY-SA 2.5 |