3
$\begingroup$

For example, given four distinct numbers $5, 6, 7, 9$ We have $2^4-1$ sums, $5, 6, 7, 9, 11, 12, 14, 13, 15, 16, 18, 22, 20, 21, 27$ which are the sums from the numbers.

But if given five distinct numbers $5, 6, 7, 8, 9$, then we see $5 + 9 = 6 + 8$, hence the possible distinct sums of them cannot be easily counted by $2^5-1$.

Is it possible to easily count all the possible distinct sums from distinct numbers? Thanks!

$\endgroup$
1
  • $\begingroup$ $2^4$ and $2^5$ if you count $0$ as a sum too. $\endgroup$
    – Henno Brandsma
    Sep 30, 2018 at 6:06

1 Answer 1

Reset to default
3
$\begingroup$

It's rather easy to count the total number of possible sums this way. But the actually different sums is a different matter: the knapsack problem says it's NP hard to determine whether some number $n$ is among those sums for a concrete set of numbers.

For superincreasing sequences all sums will be different. This has been the idea of building a public key encryption system, in fact: to modify a superincreasing sequence so that we still keep the unique sums property (so we have the maximal number of sums). $1,2,4,8, \ldots$ is superincreasing.

Counting the number of different sums in other cases could turn out to be pretty hard, I don't expect a closed formula for this to exist. But an algorithm does exist, see here e.g.

Also see this question and its answers

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.