Project Euler Problem 76

Solution

Answer: 190569291

1. Mathematical analysis

We want the number of ways to write 100 as a sum of at least two positive integers, where order does not matter.

For example:

$$5 = 4+1 = 3+2 = 3+1+1 = 2+2+1 = 2+1+1+1 = 1+1+1+1+1$$

There are 6 ways.

This is exactly the problem of counting integer partitions.

Let:

$$p(n)$$

be the number of partitions of $n$, i.e. the number of unordered ways to write $n$ as a sum of positive integers.

However, $p(n)$ includes the trivial partition:

$$n$$

itself. Since the problem asks for at least two positive integers, we must subtract 1.

So the desired quantity is:

$$p(100)-1$$

The challenge is computing $p(100)$.

Dynamic programming interpretation

This is equivalent to a coin change problem:

available “coins”: $1,2,3,\dots,99$
target sum: $100$
unlimited use of each coin
order does not matter.

Define:

$$dp[s]$$

= number of ways to make sum $s$.

Initially:

$$dp[0] = 1$$

because there is exactly one way to make zero: choose nothing.

For each integer $k$, update:

$$dp[s] \mathrel{+}= dp[s-k]$$

for all $s \ge k$.

Why does this work?

When processing number $k$:

every partition of $s-k$ can be extended by adding $k$,
and because we process numbers in increasing order, permutations are not double-counted.

This is the standard partition DP recurrence.

For the example $n=5$:

Using integers $1,2,3,4$, the DP gives:

$$dp[5] = 6$$

matching the problem statement.

For $100$, we compute:

$$p(100)-1$$

2. Python implementation

def count_partitions(n):
    """
    Count the number of ways to write n as a sum
    of at least two positive integers.
    """

    # dp[s] = number of partitions of s
    dp = [0] * (n + 1)

    # One way to form sum 0: choose nothing
    dp[0] = 1

    # Use numbers 1 through n-1
    # (excluding n itself removes the trivial partition)
    for part in range(1, n):
        for total in range(part, n + 1):
            dp[total] += dp[total - part]

    return dp[n]

# Compute the Project Euler answer
answer = count_partitions(100)
print(answer)

3. Code walkthrough

Function definition

def count_partitions(n):

Defines a function to count valid partitions of $n$.

Create DP table

dp = [0] * (n + 1)

We create an array:

$$dp[0], dp[1], \dots, dp[n]$$

initialized to zero.

Base case

dp[0] = 1

There is exactly one way to form sum 0: choose no numbers.

This base case allows larger sums to build recursively.

Iterate through allowable parts

for part in range(1, n):

We allow integers:

$$1,2,\dots,n-1$$

We intentionally exclude $n$ itself so that the partition:

$$n$$

is not counted.

Update reachable totals

for total in range(part, n + 1):
    dp[total] += dp[total - part]

If we want to form total using part, then every way to form:

$$\text{total} - \text{part}$$

extends to a new partition by adding part.

The recurrence is:

$$dp[s] \leftarrow dp[s] + dp[s-k]$$

Return answer

return dp[n]

After processing all parts, dp[n] contains the number of valid partitions.

Small example verification

For $n=5$:

Allowed parts: $1,2,3,4$

The DP counts:

$$4+1,; 3+2,; 3+1+1,; 2+2+1,; 2+1+1+1,; 1+1+1+1+1$$

Total:

$$6$$

which matches the problem statement exactly.

For $n=100$, the computation yields:

$$190569291$$

4. Final verification

A useful check:

The partition number is known to be

$$p(100)=190569292$$

Since the problem excludes the single-term partition:

$$100$$

we subtract one:

$$190569292 - 1 = 190569291$$

The magnitude is reasonable because partition numbers grow rapidly but remain far below exponential values like $2^{100}$.

Answer: 190569291