6
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ Related. Related. Brownie points for beating/matching my 13 byte, incredible inefficient (times out for \$n > 6\$ on TIO) Jelly answer \$\endgroup\$ Aug 31 at 23:30
  • \$\begingroup\$ Also related to PE 103. \$\endgroup\$
    – Bubbler
    Sep 1 at 0:34
3
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ 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) \$\endgroup\$ Sep 1 at 0:09
  • \$\begingroup\$ @Dudecoinheringaahing I didn't realise combinations_without_replacement worked - thanks for saving several bytes. \$\endgroup\$
    – emanresu A
    Sep 1 at 0:20
3
\$\begingroup\$

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

\$\endgroup\$
2
  • \$\begingroup\$ 169 bytes with two itertools related golfs. \$\endgroup\$
    – ovs
    Sep 1 at 7:33
  • \$\begingroup\$ @ovs thanks !!! \$\endgroup\$
    – wasif
    Sep 1 at 7:46
3
\$\begingroup\$

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)

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
2
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 64 46 bytes

Nθ≔¹η⊞υ¹W¬⊙υ⁼Σ↨κ²X²θ«≦⊗ηFυ¿¬&κ×ηκ⊞υ×⊕ηκ»I⊖L↨η²

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

Nθ

Input n.

≔¹η

Start with 2ᵏ=1.

⊞υ¹

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

W¬⊙υ⁼Σ↨κ²X²θ«

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

≦⊗η

Increment k.

Fυ

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.

»I⊖L↨η²

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

\$\endgroup\$
1
\$\begingroup\$

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