# Distinct Subset Sums: Extending A276661

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

• Related. Related. Brownie points for beating/matching my 13 byte, incredible inefficient (times out for $n > 6$ on TIO) Jelly answer Commented Aug 31, 2021 at 23:30
• Also related to PE 103. Commented Sep 1, 2021 at 0:34

# VyxalR, 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

• Ooh, I didn't realise that Cartesian power would work instead of combinations without replacement (as if the set includes any duplicates, it can't have distinct subset sums), so I can get my Jelly answer down to 12 bytes (and even more inefficient) Commented Sep 1, 2021 at 0:09
• @Dudecoinheringaahing I didn't realise combinations_without_replacement worked - thanks for saving several bytes. Commented Sep 1, 2021 at 0:20

# 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

• 169 bytes with two itertools related golfs.
– ovs
Commented Sep 1, 2021 at 7:33

# Python 2 (PyPy), 111102 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)

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

• Nice trick with the Ƈ, I had this Commented Sep 1, 2021 at 8:09

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

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

# 05AB1E, 16 bytes

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


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)