Make S + S + ... + S as Large as Possible!

Question

Let \$S \subset \mathbb N_{\geq0}\$ be a subset of the nonnegative integers, and let $$ S^{(k)} = \underbrace{S + S + \dots + S}_{k\ \textrm{times}} = \{ a_1 + a_2 + \dots + a_k : a_i \in S\}. $$

For example, $$\begin{align} \{1,2,3\}^{(2)} &= \{1+1, 1+2, 1+3, 2+1, 2+2, 2+3, 3+1, 3+2, 3+3\}\\ &=\{2,3,4,5,6\} \end{align}$$

If \$S\$ contains \$n\$ elements, then \$S^{(k)}\$ contains at most \$\binom{n+k-1}{k} = \frac{(n + k - 1)!}{(n-1)!k!}\$ distinct elements. If \$S^{(k)}\$ contains this number of distinct elements, we call it \$k\$-maximal. The set \$S = \{1,2,3\}\$ given in the example above is not \$2\$-maximal because \$1 + 3 = 2 + 2\$.

Challenge

Given a positive integer k, your task is to return the lexicographically earliest infinite list of nonnegative integers such that for every \$n\$ the set consisting of the first \$n\$ terms of \$S\$ is \$k\$-maximal.

You can return a literal (infinite) list/stream, you can provide function that takes a parameter i and returns the \$i\$th element of the list, or you can give any other reasonable answer.

This is code-golf so shortest code wins.

Test Data

 k | S^(k)
---+------------------------------------------------------------
 1 | 0, 1, 2,  3,   4,   5,    6,    7,     8,     9,    10, ...
 2 | 0, 1, 3,  7,  12,  20,   30,   44,    65,    80,    96, ...
 3 | 0, 1, 4, 13,  32,  71,  124,  218,   375,   572,   744, ...
 4 | 0, 1, 5, 21,  55, 153,  368,  856,  1424,  2603,  4967, ...
 5 | 0, 1, 6, 31, 108, 366,  926, 2286,  5733, 12905, 27316, ...
 6 | 0, 1, 7, 43, 154, 668, 2214, 6876, 16864, 41970, 94710, ...

For \$k=2\$ , this should return OEIS sequence A025582.

For \$k=3\$ , this should return OEIS sequence A051912.

Answer 1

JavaScript (Node.js), 102 bytes

(k,a=[],n=-1,g=_=>(h=(c,u,p)=>c?a.every(v=>v<p||h(c-1,v+u,v)):h[u]^=1)(k,a.push(++n))?n:g(a.pop()))=>g

Try it online!

Invoke f(k), it returns a function g. Each time you invoke g(), you will get the next value of k-th sequence.

Answer 2

Jelly, 15 bytes

»*@Żœcḷœċ§QƑɗƇḢ

Try it online!

Takes i and k and returns the first i elements of the kth sequence. Extremely slow.

The ith term (1-indexed) cannot exceed 1+k+..+k**(i-2) since the k-combinations without replacement of the set 0, 1, 1+k, 1+k+k**2, ..., 1+k+...+k**(i-2) has distinct sums (because each added term is strictly larger than the previously existing maximum sum) and, as the terms strictly smaller than the bound emerge, the bound for the next term will only go lower. This bound can be relaxed to max(i, k**i) by considering the cases where k=1 and k>=2.

»*@Żœcḷœċ§QƑɗƇḢ    Dyadic link. Left = i (#terms to return), Right = k
»*@                bound = max(i, k**i)
   Żœcḷ            All i-combinations of 0..bound
             ƇḢ    Filter and take the first sequence satisfying...
       œċ§QƑɗ        All k-combinations without replacement have distinct sums

Answer 3

JavaScript (ES6), 113 bytes

Expects (k)(n) and returns the first \$n\$ terms of \$S^{(k)}\$ in reverse order.

k=>n=>(g=a=>(h=(a,k,s)=>k?a.every((v,i)=>h(a.slice(i),k-1,v-~s)):h[s]^=1)(a,k)?n--?g([0,...a]):a:g(a,a[0]++))([])

Try it online!

Answer 4

Charcoal, 70 bytes

ＮθＮη≔⁰ζＷ‹Ｌυη«⊞υζ≦⊕ζ≔ＥΦＥＸＬυθ﹪Ｅθ÷κＸＬυνＬυ¬⊙κ∧ν›μ§κ⊖νΣＥκ§υμε¿⊙ε⊖№εκ≔⊟υε»Ｉυ

Try it online! Link is to verbose version of code. Takes k and n as input and outputs the first n terms. Explanation:

ＮθＮη

Input k and n.

≔⁰ζ

Start with a first trial term of 0.

Ｗ‹Ｌυη«

Repeat until enough terms have been collected.

⊞υζ

Push the next trial term to the list of terms.

≦⊕ζ

Increment the trial value.

≔ＥΦＥＸＬυθ﹪Ｅθ÷κＸＬυνＬυ¬⊙κ∧ν›μ§κ⊖νΣＥκ§υμε

Calculate all of the sums of combinations with replacement of the terms including the trial term.

¿⊙ε⊖№εκ≔⊟υε

If there are any duplicates then remove the trial term from the list.

»Ｉυ

Output the resulting list.

63 bytes by porting @ovs's Python answer:

ＮθＮη≔±¹ζ≔Ｅ⊕θ¬κεＷ‹ⅉη«≦⊕ζ≔⟦⟧δＦε⊞δ｜κ×∨⌈δ⁰Ｘ²ζ¿¬＆§ε±¹×§δ±²Ｘ²ζ«≔δε⟦Ｉζ

Try it online! Link is to verbose version of code. Takes k and n as input and outputs the first n terms. Explanation:

ＮθＮη

Input k and n.

≔±¹ζ

Start the trial term at -1 so that 0 can be considered with an initial increment on the first pass.

≔Ｅ⊕θ¬κε

Start with a list of 1 and k 0s, which are bitmasks representing the sets of sums of i elements of the empty set; the first set is the set of sums of zero elements which is always {0} while the others are empty sets.

Ｗ‹ⅉη«

Loop until n terms have been printed.

≦⊕ζ

Increment the next trial term.

≔⟦⟧δＦε⊞δ｜κ×∨⌈δ⁰Ｘ²ζ

Using the bitmasks from the terms so far, calculate the bitmasks for the sets of sums of i elements from them plus the current trial term.

¿¬∧ζ＆§ε±¹×§δ±²Ｘ²ζ«

If there are no collisions between the sums of k elements excluding the current trial term and the sums of k elements including the current trial term at least once, then...

≔δε

... save the new bitmasks, and...

⟦Ｉζ

... output the current trial term on its own line.

Answer 5

Python 3.8, 130 106 105 bytes

Thanks to Neil for pointing out a mistake.

Saved a lot of bytes by looking at @AZTECCO's Haskell answer and realizing I don't need to keep track of the maximum number of unique sums.

def f(k):
 r=1,*[0]*k;j=-1
 while 1:
  j+=1;d=0;w=[d:=i|d<<j for i in r]
  if r[k]&w[-2]<<j<1:yield j;r=w

Try it online!

Answer 6

05AB1E, 18 bytes

m‚àÝI.Æ.Δ¹ã€{ÙODÙQ

Port of @Bubbler's Jelly answer, but lacking a k-combinations without replacement builtin.

First input is \$k\$, second input is \$i\$. Outputs the first \$i\$ elements of the \$k^{th}\$ sequence.

Try it online.

Explanation:

m                  # Push the first (implicit) input to the power of the second
                   # (implicit) input: k**i
 ‚                 # Pair it together with the second (implicit) input: [i,k**i]
  à                # Pop and push the maximum
   Ý               # Pop and push a list in the range [0,max(i,k**i)]
    I.Æ            # Pop and get all i-element combinations of this list
       .Δ          # Find the first list which is truthy for:
                   #  Get all k-combinations without replacement:
         ¹ã        #   Take the current list to the cartesian power of the first input k
           €{      #   Sort each inner list
             Ù     #   Uniquify this list of lists
              O    #  Get the sum of each inner list
                   #  Check that all sums are unique:
               D   #   Duplicate the list of sums
                Ù  #   Uniquify the copy
                 Q #   Check if both lists are still equal
                   # (after which the result is output implicitly)

Answer 7

Haskell, 109 103 bytes

s#k=sum<$>mapM(\_->s)[1..k]
f=([0]!)
(n:s)!k|any(`elem`s#k)$map(+n)$s#(k-1)=(n+1:s)!k|1>0=n:(n+1:n:s)!k

Try it online!

• thanks to @Ovs for suggesting using sum<$>.. instead of map(sum)..

Essentially we search next term by checking if the sums with it creates only new sums.

• f returns an infinite list of k using an initial set [0] applied to (!)

• (n:s)!k finds all next terms indefinitely
  |any(elems#k)$... if any of ... Are in s#k try next n
  ... map(+n)$s#(k-1) permutations of k-1 + n
  else we add n to the set and we search next terms

• s#k returns all permutations of s of length k summed.
  Stolen from this answer of Laikoni

Try k=5

Try k=6