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.
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.
Hint: See if you can build P(N) up from some combination of the results prior to P(N).
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)
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 :)
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 :)
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
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!
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:
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.
Many math problems can be solved by induction.
You know the answer for a specific value, and you can find the answer for every value, if you find something that link n with n+1.
For example in your case you know that the answer for How many different ways can one be written as a sum of at least two positive integers? is just 1.
What do I mean with the link between n and n+1? Well I mean exactly that you must find a formula that, provide you know the answer for n, you will find the answer for n+1. Then, calling recursively that formula, you'll know the answer and you've done (note: this is just the mathematical part of it, in real life you might find that this approach would gave you something too slow to be practical, so you've not done yet - in this case I think you will be done).
Now, suppose that you know n can be written as a sum of at least two positive integers? in k different ways, one of which would be:
n=a1+a2+a3+...am (this sum has m terms)
What can you say about n+1? Since you would like just hints I'm not writing the solution here, but just what follows. Surely you have the same k different ways, but in each of them there will be the +1 term, one of which would be:
n+1=a1+a2+a3+...am+1 (this sum has m+1 terms)
Then, of course, you will have other k possibilities, such those in which the last term of each sum is not the same, but it will be increased by one, like:
n+1=a1+a2+a3+...(am+1) (this sum has m terms)
Thus there are at least 2k ways of writing n+1 as a sum of at least two positive integers. Well, there are other ones. Find it out, if you can :-)
And enjoy :-))
