13
\$\begingroup\$

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

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Annoyingly some of the terms are equal to the sums of powers of k but then that stops working. \$\endgroup\$
    – Neil
    Oct 20 at 22:26
  • 1
    \$\begingroup\$ So, can I just take two parameters k and i, output the i-th value in sequence k? \$\endgroup\$
    – tsh
    Oct 21 at 1:58
4
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ Defining g as you return it works for 101 bytes. \$\endgroup\$
    – emanresu A
    Oct 21 at 3:23
  • \$\begingroup\$ @emanresuA But then, you cannot use old g if you call f next time. g1 = f(1); g2 = f(2); [g1(), g1()] for example. \$\endgroup\$
    – tsh
    Oct 21 at 5:18
  • \$\begingroup\$ Oh, that makes sense. Never mind. \$\endgroup\$
    – emanresu A
    Oct 21 at 5:19
3
\$\begingroup\$

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!

\$\endgroup\$
1
  • \$\begingroup\$ k=>n=>(g=a=>(h=(k,s,p)=>k?a.every(v=>v>p||h(k-1,v-~s,v)):h[s]^=1)(k)?n--?g([0,...a]):a:g(a,a[0]++))([]) \$\endgroup\$
    – tsh
    Oct 21 at 3:48
3
\$\begingroup\$

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
\$\endgroup\$
0
3
\$\begingroup\$

Charcoal, 70 bytes

NθNη≔⁰ζW‹Lυη«⊞υζ≦⊕ζ≔EΦEXLυθ﹪Eθ÷κXLυνLυ¬⊙κ∧ν›μ§κ⊖νΣEκ§υμε¿⊙ε⊖№εκ≔⊟υε»Iυ

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

NθNη

Input k and n.

≔⁰ζ

Start with a first trial term of 0.

W‹Lυη«

Repeat until enough terms have been collected.

⊞υζ

Push the next trial term to the list of terms.

≦⊕ζ

Increment the trial value.

≔EΦEXLυθ﹪Eθ÷κXLυνLυ¬⊙κ∧ν›μ§κ⊖νΣEκ§υμε

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.

»Iυ

Output the resulting list.

63 bytes by porting @ovs's Python answer:

NθNη≔±¹ζ≔E⊕θ¬κεW‹ⅉη«≦⊕ζ≔⟦⟧δFε⊞δ|κ×∨⌈δ⁰X²ζ¿¬&§ε±¹×§δ±²X²ζ«≔δε⟦Iζ

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

NθNη

Input k and n.

≔±¹ζ

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

≔E⊕θ¬κε

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.

W‹ⅉη«

Loop until n terms have been printed.

≦⊕ζ

Increment the next trial term.

≔⟦⟧δFε⊞δ|κ×∨⌈δ⁰X²ζ

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.

¿¬∧ζ&§ε±¹×§δ±²X²ζ«

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

⟦Iζ

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

\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
6
  • 2
    \$\begingroup\$ It looks like m=m*(n+k)//n can be m+=m*k//n \$\endgroup\$
    – xnor
    Oct 21 at 15:49
  • \$\begingroup\$ Why does j start with -1? \$\endgroup\$
    – Neil
    Oct 22 at 13:53
  • \$\begingroup\$ @Neil because this way I can increment j right at the beginning of the loop, otherwise it would need to be at the end on a separate line with some indentation. (See revision 2 where I still did that) \$\endgroup\$
    – ovs
    Oct 22 at 13:56
  • 1
    \$\begingroup\$ So the fact that this version doesn't output the leading zero is a bug? \$\endgroup\$
    – Neil
    Oct 22 at 14:00
  • \$\begingroup\$ @Neil yes that is indeed a bug, thanks for pointing that out. Luckily the fix only costs a byte \$\endgroup\$
    – ovs
    Oct 22 at 14:04
2
\$\begingroup\$

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)
\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
1
  • 1
    \$\begingroup\$ sum<$>mapM ... saves a byte in (#) \$\endgroup\$
    – ovs
    Oct 22 at 10:06

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.