Project Euler Solution 76: Counting summations

Project Euler Problem 76: Counting summations asks us to find how many different ways an integer can be written as a sum of integers.

Specifically the sum has to be of at least two terms, and the numbers have to be at least 1. We are asked how many ways are there for 100.

The main complication here is not do double count anything. We have to be careful not to count 1 + 99 and 99 + 2 as two different ways. It helps to give out the rule that the numbers have to be monotonically decreasing. That means that after a certain summand there may only be summands which are of the same size or smaller.

The restriction that there has to be at least two summands is a hurdle at first. But there is only exactly one way to write it with a single summand, and that is 100. We can count all possible ways to partition 100 and then just subtract 1.

It reminds me of Solution 31: Coin sums. There one does a similar thing, but the partition is restricted due to the rather small number of coins. One could try to use the same algorithm and just supply “coins” with values 1 to 99. This doesn't work, it just takes too long to finish computing.

We can approach it better and reduce the problem. We know how many partitions we have with 0 elements: zero ways. With 1 element there is just one way. Now for 2 we have multiple options. We can split off a 2 and then divide up the remainder (0), giving 0 additional ways. Or we split off a 1 and then partition the remaining 1, yielding 1 way. So in total there are two ways, namely 2 and 1 + 1.

For 3, we can do the same. We can directly take the 3. Or we split off a 2 and partition the remaining 1 (yielding 1 partition). Or we split off a 1 and partition the remaining 2, but with the restriction that the other numbers must be smaller or equal to one. Without that restriction we would get 1 + 2, but that would overcount with the 2 + 1.

In code it looks like the following. Because this recursion would fan out quickly and take exponential time to finish, I cache the results. This way it becomes much more time efficient at the cost of a little memory.

@functools.cache
def partitions(number: int, top: int) -> int:
    if number == 0:
        return 0
    if number == 1:
        return 1
    else:
        result = sum(
            partitions(number - x, min(number - x, x)) for x in range(1, top + 1)
        )
        if number <= top:
            result += 1
        return result

The solution is to just call that function with 100 and remember to subtract the 1 for the trivial partition that we should not count.

def num_partitions(number: int) -> int:
    return partitions(number, number)


def solution() -> int:
    return num_partitions(100) - 1

That produces the correct answer in 191 ns, so it is clearly fast enough for this application.