# 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$

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 , 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).

• What do you mean by "all components are unique" ? Commented Feb 28, 2022 at 18:11
• @TheSilverDoe That sums to 63 and not 51, and so does not meet the first requirement Commented Feb 28, 2022 at 18:18
• Ok, my bad, I guess I misread. Commented Feb 28, 2022 at 18:18
• Is it even obvious that such a set always exists?
– lulu
Commented Feb 28, 2022 at 18:19
• For $x=2,4,8$ or $9$, such a set does not exist. Commented Feb 28, 2022 at 18:21

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$$.