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

= 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*(3

*n*– 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:

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

#### Comments

- Reference: The On-Line Encyclopedia of Integer Sequences (OEIS) A001318: Generalized pentagonal numbers: n*(3*n-1)/2, n=0, +- 1, +- 2, +- 3,....
- The full answer is:

363253009254357859308323315773967616467158361736338932270710864607092686080534 \

895417314045435376684389911706807452721591544937406153858232021581676352762505 \

545553421158554245989201590354130448112450821973350979535709118842524107301749 \

07784762924663654000000

*Project Euler 78 Solution last updated*

## Discussion

## No comments yet.