// you’re reading...     (11 votes, average: 5.00 out of 5) Loading...

## Project Euler 76 Solution ## 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

Project Euler 76 Solution last updated