Euler Problem 78

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



In [1]:

    
def pentagonal(N):
    a, b = 1, 2
    delta = 4
    sgn = 1
    while a <= N:
        yield sgn, a
        a += delta
        if b <= N:
            yield sgn, b
            b += delta + 1
        delta += 3
        sgn = -sgn

P = {}
modulus = 10**6
P[0] = 1
n = 0
while P[n] != 0:
    n += 1
    P[n] = 0
    for sgn, g in pentagonal(n):
        P[n] += sgn * P[n-g]
        P[n] %= modulus
print(n)

Note: Uses the pentagonal number recurrence for the partition counting function.

http://en.wikipedia.org/wiki/Pentagonal_number_theorem#Partition_recurrence