(6 votes, average: 5.00 out of 5)

## Project Euler Problem 78 Solution

#### 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, … (Sloane’s A001318).

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

#### Solution

Runs < 10 seconds in Perl.

```(\$p[0], \$n, \$i, \$m) = (1, 0, 1, 1e6);   for \$i (1..250) { #generate pentagonal numbers for generating function \$p = \$i*(3 * \$i - 1)/2; push @k, \$p, \$p+\$i; }   while (\$p[\$n++]) { #expand generating function to calculate p(n) my (\$p, \$i) = (0, 0); \$p += (\$i%4>1 ? -1 : 1 ) * \$p[\$n - \$k[\$i++]] while (\$k[\$i] <= \$n); \$p[\$n] = \$p % \$m; } print "Answer to PE78 = ",\$n-1;```

363253009254357859308323315773967616467
158361736338932270710864607092686080534
895417314045435376684389911706807452721
591544937406153858232021581676352762505
545553421158554245989201590354130448112
450821973350979535709118842524107301749
07784762924663654000000

## Discussion

### 2 Responses to “Project Euler Problem 78 Solution”

1. Hi,
How do we know that “The generating function requires at most 500 so-called generalized pentagonal numbers” ?
Thank you

Posted by Mathieu | April 3, 2013, 2:37 PM
• Yeah, I just guessed. This needs to be re-written in Python and remove the need for fixed pentagonal numbers.

Posted by Christner | April 22, 2013, 8:05 PM