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

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