## 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.

#### Answer

Slowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose*define*to reveal the answer.

|190569291|

#### Afterthoughts

- See also, Project Euler 31 Solution: Investigating combinations of English currency denominations.
- 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.