Solve in Python:
An integer partition of n is a weakly decreasing list of positive integers which sum to n.

For example, there are 7 integer partitions of 5:

[5], [4,1], [3,2], [3,1,1], [2,2,1], [2,1,1,1], [1,1,1,1,1].

Write a function named partitions which returns the number of integer partitions of n.  The function should be able to find the number of integer partitions of n for n as least as large as 100.
def partitions(n, k=1, cache={}):
    if k > n: return 0
    if n == k: return 1
    if (n,k) in cache: return cache[n,k]
    return cache.setdefault((n,k), partitions(n, k+1) + partitions(n-k, k))