(13 votes, average: 5.00 out of 5)

## Project Euler 78: Investigating the number of ways in which coins can be separated into piles

#### Problem Description

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 evenly divisible by one million.

#### Analysis

This problem is really asking to find the first term in the sequence of integer partitions that’s divisible by 1,000,000.

A partition of an integer, n, is one way of describing how many ways the sum of positive integers, ≤ n, can be added together to equal n, regardless of order. The function p(n) is used to denote the number of partitions for n. Below we show our 5 “coins” as addends to evaluate 7 partitions, that is p(5)=7.

5 = 5
= 4+1
= 3+2
= 3+1+1
= 2+2+1
= 2+1+1+1
= 1+1+1+1+1

We use a generating function to create the series until we find the required n.
The generating function requires at most 500 so-called generalized pentagonal numbers, given by n(3n – 1)/2 with 0, ± 1, ± 2, ± 3…, the first few of which are 0, 1, 2, 5, 7, 12, 15, 22, 26, 35, … (OEIS A001318).

We have the following generating function which uses our pentagonal numbers as exponents:

$1-q-q^2+q^5+q^7-q^{12}-q^{15}+q^{22}+q^{26}+\ldots$

#### Project Euler 78 Solution

Runs < 0.250 seconds in Python 2.7.

Use this link to get the Project Euler 78 Solution Python 2.7 source.