(ProjectEuler) Sum Combinations

Question

From ProjectEuler.net:

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

I have no idea how to start this...any points in the right direction or help? I'm not looking for how to do it but some hints on how to do it.

For example 5 can be written like:

4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

So 6 possibilities total.

Answer 1

Partition Numbers (or Partition Functions) are the key to this one.

Problems like these are usually easier if you start at the bottom and work your way up to see if you can detect any patterns.

• P(1) = 1 = {1}
• P(2) = 2 = {[2], [1 + 1]}
• P(3) = 3 = {[3], [2 + 1], [1 + 1 + 1]}
• P(4) = 5 = {[4], [3 + 1], [2 + 2], [2 + 1 + 1], [1 + 1 + 1 + 1]}
• P(5) = 7 ...
• P(6) = 11 ...
• P(7) = 15 ...
• P(8) = 22 ...
• P(9) = 30 ...

Hint: See if you can build P(N) up from some combination of the results prior to P(N).

Answer 2

The solution can be found using a chopping algorithm.

Use for example the 6. Then we have:

6
5+1
4+2
3+3

but we are not finished yet.

If we take the 5+1, and consider the +1 part as finished, because all other ending combinations are handled by the 4+2 and 3+3. So we need to apply the same trick to the 5.

4+1+1
3+2+1

And we can continue. But not mindlessly. Because for example 4+2 produces 3+1+2 and 2+2+2. But we don't want the 3+1+2 because we will have a 3+2+1. So we only use all productions of 4 where the lowest number is greater or equal than 2.

6
5+1
  4+1+1
    3+1+1+1
      2+1+1+1+1
        1+1+1+1+1+1
    2+2+1+1
  3+2+1
4+2
  2+2+2
3+3

Next step is to put this in an algorithm.

Ok we need a recursive function that takes two parameters. The number to be chopped and the minimal value:

func CountCombinations(Number, Minimal)
  temp = 1
  if Number<=1 then return 1
  for i = 1 to Floor(Number/2)
    if i>=Minimal then
      temp := temp + CountCombinations(Number-i, i)
  end for
  return temp
end func

To check the algorithm:

C(6,1) = 1 + C(5,1) + C(4,2) + C(3,3) = 11, which is correct.
C(5,1) = 1 + C(4,1) + C(3,2) = 7
C(4,1) = 1 + C(3,1) + C(2,2) = 5
C(3,1) = 1 + C(2,1) = 3
C(2,1) = 1 + C(1,1) = 2
C(1,1) = 1
C(2,2) = 1
C(3,2) = 1
C(4,2) = 1 + C(2,2) = 2
C(3,3) = 1

By the way, the number of combinations of 100:

CC(100) = 190569292
CC(100) = 190569291 (if we don't take into account 100 + 0)

Answer 3

A good way to approach these is not get fixated on the '100' but try to consider what the difference between totalling for a sum n and n+1 would be, by looking for patterns as n increases 1,2,3....

I'd have a go now but I have work to do :)

Answer 4

Like most problems in Project Euler with big numbers, the best way to think about them is not to get stumped with that huge upper bound, and think of the problem in smaller terms, and gradually work your way up. Maybe, on the way you'll recognize a pattern, or learn enough to get you to the answer easily.

The only other hint I think I can give you without spoiling your epiphany is the word 'partition'.

Once you've figured that out, you'll have it in no time :)

Answer 5

one approach is to think recursive function: find permutations of a numeric series drawn from the positive integers (duplicates allowed) that add up to 100

• the zero is 1, i.e. for the number 1 there are zero solutions
• the unit is 2, i.e for the number 2 there is only one solution

another approach is to think generative function: start with the zero and find permutation series up to the target, keeping a map/hash or the intermediate values and counts

you can iterate up from 1, or recurse down from 100; you'll get the same answer either way. At each point you could (for a naive solution) generate all permutations of the series of positive integers counting up to the target number minus 1, and count only those that add up to the target number

good luck!

Answer 6

Notice: My maths is a bit rusty but hopefully this will help...

You are going well with your break down of the problem.

Think Generally:

• A number n can be written as (n-1)+1 or (n-2)+2
• You generalise this to (n-m)+m
• Remember that the above also applies to all numbers (including m)

So the idea is to find the first set (lets say 5 = (5-1)+1) and then treat (5-1) as a new n...5 = 4 +1...5 = ((4-1)+1)+1. The once that is exhausted begin again on 5 = 3 + 2....which becomes 5 = ((3-1)+1)+2 ....= 2+1+2....breaking down each one as you go along.