I'm trying to find a partition of natural number N whereby
- we can generate a partition for all natural numbers less than N from the partition elements.
- The number of elements in the partition should be as small as possible.
For example, if N is 8, I believe the partition is {1,2,4,1} since I can form a partition for all natural numbers less than 8 from the elements like the below.
1 = 1, 2 = 2, 3 = 1+2, 4 = 4, 5 = 1+4, 6 = 2+4, 7 = 1+2+4
I simply put the power of 2s (ex {1,2,4}) until the sum of them are less than or equal to N. Then, put the remainder(ex {1}) to make sum of all elements equal to N. I'd like to know if this method is the right approach to get a partition with the smallest number of elements. Is there any theorem related to it? It would be great if anyone can help me to prove whether my method is right or wrong. Thanks!