2
$\begingroup$

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

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

1 Answer 1

2
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ Thanks, I implemented it in code and it works perfectly! $\endgroup$
    – knaccc
    Commented Feb 28, 2022 at 19:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .