Consider the integer set \$S = \{3, 5, 6, 7\}\$. If we list all \$2^n\$ subsets of \$S\$ (its powerset) and calculate their sums, we get
$$ \mathcal{P}(S) = \{\emptyset, \{3\}, \{5\}, \{6\}, \{7\}, \{3, 5\}, \{3, 6\}, \{3, 7\}, \{5, 6\}, \{5, 7\}, \{6, 7\}, \{3, 5, 6\}, \{3, 5, 7\}, \{3, 6, 7\}, \{5, 6, 7\}, \{3, 5, 6, 7\}\} \\ \sum_{s \in \mathcal{P}(S)} s = \{0, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 21\} $$
You'll note that this set of sums is distinct - no element is repeated. We'll say that \$S\$ is a distinct subset sum set. Note that we're only considering sets containing positive integers for this.
In fact, for \$n = 4\$, \$k = 7\$ is the smallest positive integer such that there is a set \$S\$ containing \$n\$ distinct elements from the set \$\{1, 2, ..., k\}\$ and that \$S\$ is a distinct subset sum set. The values of \$k\$ for \$n = 0, 1, 2, 3\$ are:
\$n\$ | \$k\$ | \$S\$ |
---|---|---|
\$0\$ | \$0\$ | \$\emptyset\$ |
\$1\$ | \$1\$ | \$\{1\}\$ |
\$2\$ | \$2\$ | \$\{1,2\}\$ |
\$3\$ | \$4\$ | \$\{1,2,4\}\$ |
For any given \$n\$, we can say that \$2^{n-1}\$ is an upper bound, as the set \$\{2^0, 2^1, ..., 2^{n-1}\}\$ is always a distinct subset sum set.
However, as shown above, this upper bound can be improved. In fact, one of the current best upper bounds is the Conway-Guy sequence (A005318), given by:
$$ a_0 = 0, a_1 = 1\\ a_{n+1} = 2a_n - a_{n - \lfloor 1/2 + \sqrt{2n} \rfloor} $$
However, it's been shown that \$a_{67} = 34808838084768972989\$ can be improved as a bound to \$34808712605260918463\$, so the Conway-Guy sequence is currently only an upper bound (and a non-optimal one at that), rather than the exact terms. The exact terms are given by A276661.
This sequence has only been proven to be optimal up to \$n = 9\$. Your task is to improve this.
Your program should take a non-negative integer \$n\$ and output the smallest integer \$k\$ such that there exists a distinct subset sum set \$S\$ such that, for all elements \$S_i\$, \$1 \le S_i \le k\$. Note that this is not the Conway-Guy sequence; if given \$n = 67\$ as an input, the output should not be \$34808838084768972989\$.
Your program may fail practically due to integer constraints (e.g. if the output exceeds your language's integer maximum), but should work theoretically for all \$n\$.
This is code-golf, so the shortest code in bytes wins.
Additionally, I will offer a bounty for the answer for which:
- it can produce the correct output for a value \$x > 9\$ within a minute (time using TIO if possible), and
- it can produce the correct output for all values \$1 \le i \le x\$ within a minute for each
The bounty will be awarded to the answer which can do this for the highest \$x\$. The amount I'll award will depend on the exact value of \$x\$ (e.g. \$x = 20\$ will be awarded more than \$x = 10\$), but it will be at least 150 reputation. Once someone can produce the output for \$x = 10\$, I'll wait 2 weeks for any answers to try to beat it, then start the bounty.
Test cases
n k
0 0
1 1
2 2
3 4
4 7
5 13
6 24
7 44
8 84
9 161