How to split a natural number $x$ into components, such that they sum to $x$ and a sub-list exists which can sum to any value less than $x$

Question

For a natural number $x$ (excluding zero), what method can be used to determine the smallest list of natural number components such that:

1. The sum of all components is $x$
2. For any natural number $a$ such that $1\leq a <x$, there exists a sub-list of those components that sum to $a$, where no component can be used more than once (unless that component appears more than once in the list)

For example, if $x$ is 63, we'd determine the components {1, 2, 4, 8, 16, 32}.

If $x$ is 51, we'd determine the components {1, 2, 3, 6, 13, 26}.

If $x$ is 2, we'd determine the components {1, 1}.

(This is useful for "range proofs" in cryptography, where you need to prove that a secret number is within a certain range by proving the secret must be the sum of a sub-list of specified components. If there is a deterministic method to find such a list of components for some value of $x$, then both prover and verifier can determine the list independently, rather than the prover having to transmit the list to the verifier).

Answer 1

The length of a successful list must be at least $\lceil \log_2 (x+1)\rceil$. This is because if we take a successful list of length $k$, and generate all $2^k-1$ sums of nonempty sublists, you will see all numbers in $\{1,\dots,x\}$, implying $2^k-1\ge x$.

Here is a way to get a list of that optimal size. Let $h=\lfloor x/2\rfloor$. Recusively find a list summing to $h$ which generates all numbers in $\{1,\dots,h\}$, then append $x-h$ to that list.

Using the fact that $\lceil\log_2(x+1)\rceil=\lceil\log_2(\lfloor x/2\rfloor+1)\rceil +1$ for any positive integer $x$, you can prove by induction that my algorithm produces a list with the optimal size. Indeed, $\log_2(x+1)$ is the number of bits of $x$'s binary representation, and $\lfloor x/2\rfloor$ always has exactly one fewer bit than $x$.