# 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?

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