Project Euler Solution 78: Coin partitions

Project Euler Problem 78: Coin partitions throws us back to partitions of integers, but now with a more demanding task.

In Solution 76: Counting summations we looked at the number of ways that we can partition 100 into integers. We can define the number of partitions as $p(n)$ and the answer to Problem 76 was $p(100) - 1$. In this problem here we have to find the smallest number $n$ such that $p(n)$ becomes divisible by 1,000,000.

Trying to use the algorithm from Solution 76 is not feasible, it just takes too long for each time. We need something more clever. Luckily this partition function has a recurrence relation which make it efficient to calculate.

Using the combination of recursion and a cache it is straightforward to implement the recurrence relationship into a function:

@functools.cache
def partitions(number: int) -> int:
    if number == 0:
        return 1
    elif number < 0:
        return 0
    else:
        result = 0
        for k in itertools.count(1):
            part_1 = partitions(number - k * (3 * k - 1) // 2)
            part_2 = partitions(number - (-k) * (3 * (-k) - 1) // 2)
            sign = +1 if k % 2 == 1 else -1
            result += sign * (part_1 + part_2)
            if not part_1 and not part_2:
                break
        return result

For the solution we just iterate through all numbers and then stop when it becomes divisible by 1,000,000.

def solution() -> int:
    for n in itertools.count(5):
        if partitions(n) % 1_000_000 == 0:
            return n

This finds the solution in 5.0 s, which likely is okay.