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:

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