78. Coin partitions.md

78. Coin partitions

Question

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.

Solution

Naively thought this is another "copy and paste" problem just like 77. Prime summations. However, the number is much larger here. If we look at the solution of 76. Counting summations, to calculate f(n), we use pre-calculated/cached values so that f(n) is obtained through n operations i.e. O(n). This becomes incredibly slow when n gets large.

One of the ways to solve this problem is to use Pentagonal number theorem. Then we have

Also, . Notice that g(k) is a power function therefore much fewer operations needed to obtain p(n). Follow up will focus on how to obtain this recurrence relation.

def p78():

    def partition(n):
        pn = 0
        for k in range(1, n + 1):
            gk = k * (3 * k - 1) // 2
            if gk > n: break
            pn += (-1) ** (k - 1) * p[n - gk]

            k *= -1
            gk = k * (3 * k - 1) // 2
            if gk > n: break
            pn += int((-1) ** (k - 1)) * p[n - gk]
        p[n] = pn
        return pn

    n, pn = 0, 1
    p = {n: pn}
    while pn % 1000000 != 0:
        n += 1
        pn = partition(n)
    return n

Answer

55374