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.

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.

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;

Comments

The full answer is:
363253009254357859308323315773967616467
158361736338932270710864607092686080534
895417314045435376684389911706807452721
591544937406153858232021581676352762505
545553421158554245989201590354130448112
450821973350979535709118842524107301749
07784762924663654000000