How many different ways can one hundred be written as a sum of at least two positive integers?
I am not getting algo. please any one can give me write solution of this problem
Printable View
How many different ways can one hundred be written as a sum of at least two positive integers?
I am not getting algo. please any one can give me write solution of this problem
That's not how this forum works.Quote:
Originally Posted by freakycoder
Does "algo" mean algorithm?Quote:
Originally Posted by freakycoder
Well...
This is related to a well-known topic in number theory: Integer Partitions
Here is an illustration of how calculation of a partition number (size of the set of partitions of a positive integer) relates to your assignment:
Let's look at the number of ways of writing a particular number, 5, as the sum of positive integers:
Note that p(5) = 7 and the seven ways of writing 5 as the sum of positive integers are:
5
4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1
Note also that, except for the first one, each of these lines (called parts or partitions of the number) consists of the sum of two or more positive integers.
Making a slight inductive leap (without formal proof):
The algorithm for finding the number of ways of writing 100 as the sum of two or more positive integers is:
- Calculate p(100).
- The answer is p(100)-1.
Finally, note that using partition number calculations as outlined in the Wikipedia article (and myriads of other references) depends on the following convention:
Two sums that differ only in the order of their terms are considered to be the same partition.
That is, 2+3 is the same as 3+2, so you don't count that as two different partitions.
Similarly, 2+2+1 is the same as 2+1+2, and is the same as 1+2+2.
Etc.
Cheers!
Z