# Project Euler Problem 78 Solution

## Question

Let p(n) represent the number of different ways in which n coins can be separated into piles. For example, five coins can separated into piles in exactly seven different ways, so p(5)=7.

 OOOOO OOOO   O OOO   OO OOO   O   O OO   OO   O OO   O   O   O O   O   O   O   O

Find the least value of n for which p(n) is divisible by one million.

import Data.Array
import Data.List (sort)

pentagonals :: [Integer]
pentagonals = sort [n*(3*n - 1) quot 2 | n <- [-250..250], n /= 0]

cache :: Array Integer Integer
cache = array (0, 100000) [(x, partition x) | x <- [0..100000]]

partition :: Integer -> Integer
partition n | n <= 1 = 1
| otherwise = sum [s * (cache ! (n - p)) | (s, p) <- zip (cycle [1, 1, -1, -1]) (takeWhile (<= n) pentagonals)]

main :: IO ()
main = print $head [i | (i, p) <- assocs cache, p rem 1000000 == 0] $ ghc -O2 -o coin-partitions coin-partitions.hs
$time ./coin-partitions real 0m1.368s user 0m1.352s sys 0m0.016s ## Python #!/usr/bin/env python from itertools import * def pentagonal(n): return n*(3*n - 1) / 2 partitions = {} generalized_pentagonals = sorted(map(pentagonal, list(range(-250, 250))))[1:] def partition(n): if n <= 1: return 1 if n not in partitions: signs = cycle([1, 1, -1, -1]) pentagonals = takewhile(lambda p: p <= n, generalized_pentagonals) partitions[n] = sum(sign * partition(n - p) for sign, p in zip(signs, pentagonals)) return partitions[n] def main(): print(next((n for n in count(0) if partition(n) % 1000000 == 0))) if __name__ == "__main__": main() $ time python3 partitions.py
real   0m12.142s
user   0m12.141s
sys    0m0.000s