Project Euler Problem 76 Solution

Question

It is possible to write five as a sum in exactly six different ways:

\begin{aligned} &4 + 1 \\ &3 + 2 \\ &3 + 1 + 1 \\ &2 + 2 + 1 \\ &2 + 1 + 1 + 1 \\ &1 + 1 + 1 + 1 + 1 \end{aligned}

How many different ways can one hundred be written as a sum of at least two positive integers?

Haskell

import Data.Array

change :: Integer -> Integer -> Integer
change t c = cache ! (t, c) where
    cache = array ((0, 0), (t, c)) [((i, j), f i j) | i <- [0..t], j <- [0..c]]
    f _ 1 = 1
    f t' c' = sum [cache ! (t' - i*c', c' - 1) | i <- [0..t' `quot` c']]

main :: IO ()
main = print $ change 100 99

$ ghc -O2 -o counting-summations counting-summations.hs
$ time ./counting-summations
real   0m0.004s
user   0m0.000s
sys    0m0.004s

Python

#!/usr/bin/env python

partitions = {}
def partition(n):
    if n < 0: return 0
    if n == 0: return 1
    if n not in partitions:
        # http://mathworld.wolfram.com/PartitionFunctionP.html
        partitions[n] = sum([(-1)**(k+1) * (partition(n - (k * (3 * k - 1) // 2))
            + partition(n - (k * (3 * k + 1) // 2))) for k in range(1, n+1)])
    return partitions[n]

def main():
    print(partition(100) - 1)

if __name__ == "__main__": main()

$ time python3 partitions.py
real   0m0.022s
user   0m0.014s
sys    0m0.007s