# Partition and power of 2s

I'm trying to find a partition of natural number N whereby

1. we can generate a partition for all natural numbers less than N from the partition elements.
2. 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!

-

This does yield the smallest size partition (though there might be other partitions of this size that do the job - but yours definitely works). Notice that the size of your partition is $\lceil \log_2(N+1) \rceil$ (as you can check); we can show that no smaller partition will work.
Suppose that you have a partition with $k<\lceil \log_2(N+1) \rceil$ parts, so that $k < \log_2(N+1)$ in particular. The number of subsets of your partition is $2^k$, so even if they all had different sums, the total number of sums that can be achieved (as a sum of a subpartition) is at most $2^k < 2^{\log_2(N+1)} = N+1$; in other words, the total number of sums that could be achieved is at most $N$. But the two sums $0$ and $N$ are definitely achieved, so there must be some natural number between $1$ and $N-1$ that can't be achieved.