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.

Haskell

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