Distinct Subset Sums: Extending A276661

Question

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

Answer 1

Vyxal R, 13 bytes

λ?↔'ṗv∑:U⁼;;ṅ

Try it Online!

Outputs in a singleton list.

λ          ;ṅ # First integer for which the following is true:
   '      ;   # Any of...
 ?↔           # combinations_with_replacements(1..n,input)
   '      ;   # Has the property that...
    ṗv∑       # Sums of all subsets
       :U⁼    # Are all unique

Answer 2

Python 3.8 (pre-release), 169 bytes

from itertools import*
f=lambda i,n=2:any(len(k:=[*map(sum,chain(*[combinations(x,r)for r in range(n)]))])==len({*k})for x in product(*[range(1,n)]*i))and~-n or f(i,n+1)

Try it online!

Mighty itertools

-15 thanks to @ovs

Answer 3

Python 2 (PyPy), 111 102 96 bytes

Finishes for \$n=7\$ in three seconds, every larger \$n\$ takes too long on TIO.

f=lambda n,i=1,s=[(0,1)]:n>max(zip(*s)[0])and-~f(n,i+1,s+[(w+1,l|l<<i)for w,l in s if l<<i&l<1])

Try it online!

The list s keeps track of all valid sets up to size k, storing a set as its length and the possible sums represented by a bitmask. This improves performance over regular sets and makes adding a new number as simple as l|l<<i.

With some small optimizations this finishes in under a second for \$n=7\$: Try it online!
\$n=8\$ is still far out on TIO (1m30s and 15GB RAM locally)

Answer 4

Jelly, 11 bytes

ṗŒP§QƑƊƇ¥1#

Try it online!

A monadic link taking and returning an integer. Terribly inefficient since it takes the powerset of the Cartesian power. Replacing ṗ with œc improves efficiency at the cost of a byte, but still very slow.

Answer 5

JavaScript (ES10), 136 bytes

Slightly shorter. Much slower.

n=>(g=k=>{for(v=++k**n;v--*!(new Set([...Array(n)].reduce((a,_,i)=>a.flatMap(x=>[x,x+v/k**i%k|0]),[0])).size>>n););return~v?0:1+g(k)})``

Try it online!

---

JavaScript (ES7), 138 bytes

n=>(g=k=>{for(v=++k**n;v--*!(new Set([...Array(n)].reduce((a,_,i)=>[...a,...a.map(x=>x+v/k**i%k|0)],[0])).size>>n););return~v?0:1+g(k)})``

Try it online!

Answer 6

Charcoal, 64 46 bytes

Ｎθ≔¹η⊞υ¹Ｗ¬⊙υ⁼Σ↨κ²Ｘ²θ«≦⊗ηＦυ¿¬＆κ×ηκ⊞υ×⊕ηκ»Ｉ⊖Ｌ↨η²

Try it online! Link is to verbose version of code. Too slow to do n>6 on TIO. Explanation:

Ｎθ

Input n.

≔¹η

Start with 2ᵏ=1.

⊞υ¹

The empty set has one subset sum, {0}, represented here as a bitmask of 2⁰=1.

Ｗ¬⊙υ⁼Σ↨κ²Ｘ²θ«

Repeat until a subset sum set of size 2ⁿ is found.

≦⊗η

Increment k.

Ｆυ

Loop over all of the sets so far.

¿¬＆κ×ηκ

If adding k to each subset sum (achieved by shifting the bitmask left by k bits) does not duplicate any existing sum, then ...

⊞υ×⊕ηκ

... add the combined subset sum set to the list.

»Ｉ⊖Ｌ↨η²

Extract the value of k needed to get a set of size n.

Answer 7

05AB1E, 16 bytes

Āi∞.ΔLIãεæODÙQ}à

Try it online or verify increasing test cases until it times out.

Explanation:

Āi              # If the (implicit) input is not 0:
  ∞.Δ           #  Find the first positive integer which is truthy for:
     L          #   Pop the integer, and push a list in the range [1,n]
      Iã        #   Take the cartesian power of the input-integer
        ε       #   Map each inner list to:
         æ      #    Take the powerset of this list
          O     #    Sum each inner list
                #    Check if all items are unique by:
           D    #     Duplicating the list
            Ù   #     Uniquify the copy
             Q  #     Check if the lists are still the same
        }à      #   After the map: check if any were truthy (by taking the max)
                #  (after which the integer is output implicitly as result)
                # (implicit else: output the implicit input; the 0)