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

See Problem 31 as it is the same type of solution.

Solution

Runs < 1 second.

my $target = 100;
my @n = (1..99);
my @ways = (1);
 
for $i (@n) {
  $ways[$_] += $ways[$_-$i] for $i..$target;
}
print "Answer to PE76 = $ways[$target]";

Comments

We were able to re-use our code from Problem 31.