## Project Euler 76: Number of ways a number can be written as a sum of at least two positive integers

#### Problem Description

It is possible to write five as a sum in exactly six different ways:

4 + 1

3 + 2

3 + 1 + 1

2 + 2 + 1

2 + 1 + 1 + 1

1 + 1 + 1 + 1 + 1

How many different ways can one hundred be written as a sum of at least two positive integers?

#### Analysis

Same solution as used for solving Problem 31. Instead of using a set of predefined coins we use the counting numbers from 1 to 99. The result follows the number of partitions of n (the partition numbers: 1, 2, 3, 5, 7, 11, 15, 22, 30, …) minus one since we require two or more positive integers for a sum and exclude the the number n by itself.

#### Project Euler 76 Solution

Runs < 0.010 seconds in Python 2.7.Use this link to get the Project Euler 76 Solution Python 2.7 source.

#### Afterthoughts

- See also, Project Euler 31 Solution:
- Reference: The On-Line Encyclopedia of Integer Sequences (OEIS) A000041: a(n) = number of partitions of n (the partition numbers).

*Project Euler 76 Solution last updated*

## Discussion

## No comments yet.