How can the smallest set of integers be generated such that the sums cover a given set?

Question

I have a set of positive integers S. I want to generate a set of positive integers T such that every member of S is the sum of some combination of members from T. I am looking for the smallest possible T.

I.e. Given $S = \{x|x \in \Bbb N\}$, generate the smallest possible $T = \{y|y \in \Bbb N\}$ such that for each $x$ in $S$ there exists a $K \subset T$ where $x = \sum_{y\in K} y$

This is for a real-world application. A solution that is close to optimal is good enough. The size of $S$ is ~$2^{30}$

Does this problem have a well-known name? I'm not getting anywhere with google. Can you point me in the right direction?

Answer 1

Generate $T$ by stages. Say $A=\{a_1<a_2<a_3<\dots\}$. In stage $1$, put $a_1\in T$. In stage $2$, put $a_2\in T$. At the beginning of stage $n$, we have an approximation to $T$. If $a_n$ is sum of distinct elements of this approximation, we are done with this stage, and go to the next one. Otherwise, add $a_n\in T$, and this concludes stage $n$. At each stage we are adding elements only if they are needed. The set we get at the end is the "smallest" $T$ you require. Note that smallness here is assuming $T\subset S$. Otherwise, there may not be a smallest set. For instance, if $S=\{1,3\}$ then $T_1=S$ and $T_2=\{1,2\}$ work and are $\subseteq$-incomparable.

Answer 2

This is probably too late and too inefficient to be of use, but I was able to brute-force in python a list of possible bases for a relatively small S using binary as an upper bound for the amount of elements in the basis.

It relies on the fact that if M is the maximum element in S, then the set T = {1, 2, 4, ..., 2^{⌈log₂(M+1)⌉-1}} is necessarily a potential solution because n bits of binary can represent all integers in 0...2ⁿ-1. Thus, if there is a more optimal T, it must have less elements than the binary basis.

I'm hoping it will at least provide some inspiration for people looking for a solution.

#!/usr/bin/python3

from itertools import chain, combinations
from math import log2, ceil

def powerset(iterable):
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

def test_bases(iterable):
    max_element = max(iterable)
    rec_count = int(ceil(log2(max_element+1)))
    def inner(m, c, t=None):
        for x in range(0, m+1):
            tx = (x,) if t is None else t + (x,)
            if c > 1:
                yield from inner(x, c-1, tx)
            else:
                yield tx
    yield from inner(max_element, rec_count)

S = {0, 3, 4, 6, 7, 9, 10, 12, 13, 14, 16, 17, 19, 20, 22, 23, 24, 26, 27, 29, 30, 32, 33, 34, 36, 37, 39, 40, 42, 43, 46}

with open("bases.csv", "w") as o:
    for T in test_bases(S):
        sumsT = set(sum(t) for t in powerset(T))
        if S.issubset(sumsT):
            print(*T, sep=",", file=o)