Compute the number of ways how you can express a number as a sum For a given natural number n, compute the number of ways how one can express n as a sum of positive natural numbers. For example, for n = 1 there is just one way. For n = 4 we have 5 possible ways:

1 + 1 + 1 + 1
1 + 1 + 2
1 + 3
2 + 2
4


The ordering of terms in a sum doesn't matter, so 1 + 3 and 3 + 1 are considered the same. Your program should be effective enough to return the result for n = 1000 in order of minutes.

The winner will the solution with most up-votes in (at least) 2 weeks.
Haskell, 170 148

An efficient Haskell version using a generating function with Memoization. Solve instantaneously the problem for n = 1000. No precision issues even with large numbers:

time ./partitions 10000
36167251325636293988820471890953695495016030339315650422081868605887952568754066420592310556052906916435144
./partitions 10000  17.02s user 0.00s system 100% cpu 17.021 total


The code

generalizedPentagonal = map pentagonal $ [1..] &gt;&gt;= \i-&gt;[i,-i]
    where pentagonal n = (3*n^2-n)`quot`2

partitions = (map partitions' [0..] !!)
    where partitions' 0 = 1
          partitions' n = sum . alternate . map partitions . takeWhile (&gt;=0) . map (n-) $ generalizedPentagonal
          alternate = zipWith (*) (concat . repeat $ [1,1,-1,-1])


Code-golf version

p=(map a[0..]!!)where a 0=1;a n=sum.zipWith(*)(concat.repeat$[1,1,-1,-1]).map p.takeWhile(&gt;=0).map(n-).map(\n-&gt;(3*n^2-n)`quot`2)$[1..]&gt;&gt;= \i-&gt;[i,-i]


Efficiency improvements

Replace the memoization with an Array instead of a list:

import Data.Array
[...]
bnd = (0,10000)
partitions = (array bnd [(i, partitions' i) | i &lt;- range bnd] !)
[...]


Time for partitions 10000 drop from 17s to 960ms

Results

Interpreted:

partitions 1000
24061467864032622473692149727991
(0.11 secs, 21833064 bytes)


Compiled:

time ./partitions 1000   
24061467864032622473692149727991
./partitions 1000  0.08s user 0.00s system 99% cpu 0.084 total


Useful links


The generating function
Generalized pentagonal numbers