Euler – Coder.si

Coin partitions

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

def run(divisor=1000000):
    # divisor == values divisible by
    limit = 10**5

    p = [0] * limit
    p[0] = 1

    for i in range(1, limit):
        j = 1
        k = 1
        s = 0
        while j > 0:
            j = i - (3 * k * k + k) // 2
            if j >= 0:
                s -= p[j] * (-1)**k
            j = i - (3 * k * k - k) // 2
            if j >= 0:
                s -= p[j] * (-1)**k
            k += 1
        p[i] = s % divisor
        if not p[i]:
            return i