Generate *all* coprime tuples

Question

Given integers k and n, generate a sequence of n unique k-tuples of pairwise coprime integers. Every such tuple must occur once eventually, that is, for any existing k-tuple of pairwise coprime integers, some n will eventually generate it.

The output may be printed or evaluated in any list/tuple-like form.

Definitions

• Two numbers a and b are coprime if gcd(a, b) = 1, i.e. they share no common divisor other than 1.
• A tuple of k numbers (a1, a2, ..., ak) is pairwise coprime if every pair of numbers in the tuple is coprime.

Examples

 k =  1, n =  5 -> [[1],[2],[3],[4],[5]]
 k =  2, n =  7 -> [[2,1],[3,1],[3,2],[4,1],[4,3],[5,1],[5,2]]
 k =  3, n = 10 -> [[3,2,1],[4,3,1],[5,2,1],[5,3,1],[5,3,2],[5,4,1],[5,4,3],[6,5,1],[7,2,1],[7,3,1]]
 k =  4, n =  2 -> [[5,3,2,1],[5,4,3,1]]
 k =  5, n =  0 -> []

Notes

• Standard code golf rules, shortest code wins.
• k is assumed to be positive, and n non-negative.
• The numbers within each tuple must be positive, distinct, and may appear in any order.
• Uniqueness is up to ordering: e.g. (1,2,3) is the same as (1,3,2).
• Good luck and have fun!

Answer 1

05AB1E, 13 bytes

I think it has been 389 days since I last posted something here haha. There is definitely some golfing potential left in this program.

Code

Uses the 05AB1E-encoding.

∞æ¹ùʒPy.¿Q}²£

Try it online!

Explanation

It is worth noting that for two numbers \$n, m \in \mathbb{Z}^+\$ that:

$$ \tag{1} \label{1} \gcd(n, m) \cdot \text{lcm}(n, m) = n \cdot m $$

This means that for two numbers \$n, m \in \mathbb{Z}^+\$ where the \$\gcd(n, m) = 1\$, we can conclude that the \$\text{lcm}(n, m) = n \cdot m\$.

Furthermore, the \$\gcd\$ function is a multiplicative function, which means that if \$n_1\$ and \$n_2\$ are relatively prime, then:

$$ \gcd(n_1 \cdot n_2, m) = \gcd(n_1, m) \cdot \gcd(n_2, m) $$

From this, we obtain the fact that:

$$ \tag{2} \label{2} \gcd(a, bc) = 1 \iff \gcd(a, b) = 1 \wedge \gcd(a, c) = 1 $$

Let us denote a \$k\$-tuple of positive integers as \$S = \{x_1, x_2, \dots, x_k\}\$. A set \$S\$ is pairwise coprime, if and only if:

$$ \tag{3} \label{3} \forall a, b \in S \wedge a \not = b \rightarrow \gcd(a, b) = 1 $$

Using Equations \$\eqref{1}, \eqref{2}\$ and \$\eqref{3}\$, we can conclude that a set \$S = \{x_1, x_2, \dots, x_k\}\$ is pairwise coprime, if and only if:

$$ \text{lcm}(x_1, x_2, \dots, x_k) = \prod_{x \in S} x $$

Code Explanation

∞æ¹ùʒPy.¿Q}²£

∞æ              # Powerset of the infinite list [1, ..., ∞].
  ¹ù            # Keep only lists of length k.
    ʒ     }     # Filter. Keep lists where the
     P          #   product of the list
         Q      #   is equal to
      y.¿       #   the least common multiple of the list
           ²£   # Retrieve the first n elements.

Answer 2

Husk, 9 bytes

↑fËoε⌋`ṖN

Try it online!

Explanation

A straightforward solution, not the most exciting.

↑fËoε⌋`ṖN  Implicit inputs, say k=3, n=2.
        N  Natural numbers: [1,2,3,4,..
      `Ṗ   All k-element subsets: [[1,2,3],[2,3,4],[1,3,4],..
           ` flips the arguments of Ṗ since it expects the number first.
 f         Keep those that satisfy this:
  Ë          All pairs x,y (not necessarily adjacent) satisfy this:
     ⌋         their gcd
   oε          is at most 1.
           Result is all pairwise coprime subsets: [[1,2,3],[1,3,4],..
↑          Take the first n: [[1,2,3],[1,3,4]]

Answer 3

Jelly, 16 bytes

‘×ÆNœcŒcg/€$ÐṂḣ⁸

A dyadic Link accepting n on the left and k on the right.

Try it online!

There must be a better way than this inefficient monstrosity! It'll time out for quite small inputs since it inspects all k-tuples of the natural numbers up to the (n+1)*k-th prime! (The +1 is only needed to handle n=0.)

Answer 4

Wolfram Language (Mathematica), 106 bytes

(s=Range[#2#];If[#==1,List/@s,SortBy[Select[s~(S=Subsets)~{#},Union[GCD@@@#~S~{2}]=={1}&],Last][[;;#2]]])&

Try it online!

Answer 5

Python 3, 153 bytes

lambda n,k,R=range:[[*t,r]for r in R(n+k+2)for t in combinations(R(1,r),k-1)if all(sum(x%i<1for x in[*t,r])<2for i in R(2,r))][:n]
from itertools import*

Try it online!

A function that takes n, k as arguments and returns out the list of n co-prime k-tuples.

The tuple are generated with increasing maximum, so it's guaranteed that every co-prime tuple will eventually be printed as n increases.

Answer 6

Charcoal, 58 bytes

ＮθＮη≔⁰ζ⊞υ⟦⟧Ｗ‹ＬΦυ⁼Ｌκθη«≦⊕ζＦΦυ⬤κ⬤…²ζ∨﹪μξ﹪ζξ⊞υ⁺⟦ζ⟧κ»Ｉ…Φυ⁼Ｌιθη

Try it online! Link is to verbose version of code. Explanation:

ＮθＮη

Input k and n.

≔⁰ζ⊞υ⟦⟧

Start the master list with a 0-tuple whose largest number is 0.

Ｗ‹ＬΦυ⁼Ｌκθη«

Repeat until we have at least k n-tuples.

≦⊕ζ

Increment the candidate number.

ＦΦυ⬤κ⬤…²ζ∨﹪μξ﹪ζξ

Filter out all of the existing tuples where at least one member has a common factor with the candidate.

⊞υ⁺⟦ζ⟧κ

Prepend the candidate to each remaining tuple and push all the resulting tuples back to the master list.

»Ｉ…Φυ⁼Ｌιθη

Print the first n k-tuples.

Answer 7

JavaScript (ES6), 143 bytes

Takes input as (k)(n).

(k,x=0)=>F=n=>n?(g=a=>x>>i?x>>i++&1?a.some(x=>(C=(a,b)=>b?C(b,a%b):a>1)(x,i))?[]:g([...a,i]):g(a):b=a)(i=[],x++).length-k?F(n):[b,...F(n-1)]:[]

Try it online!

Commented

( k,                        // outer function taking k
  x = 0                     // x = bit mask of integers to include in the tuple
) =>                        // 
F = n =>                    // F = recursive function taking n
n ?                         // if n is not equal to 0:
  ( g = a =>                //   g is a recursive function taking a[]:
      x >> i ?              //     if x is greater than or equal to 2**i:
        x >> i++ & 1 ?      //       if the i-th bit is set in x:
          a.some(x =>       //         for each value x in a[]:
            ( C = (a, b) => //           C tests whether a and b are coprime:
              b ?           //             if b is not equal to 0:
                C(b, a % b) //               recursive call with (b, a mod b)
              :             //             else:
                a > 1       //               true if *not* coprime
            )(x, i)         //           initial call to C with (x, i)
          ) ?               //         end of some(); if truthy:
            []              //           abort by returning an empty array
          :                 //         else:
            g([...a, i])    //           append i to a[] and call g again
        :                   //       else:
          g(a)              //         just call g with a[] unchanged
      :                     //     else:
        b = a               //       done: return a[] and save it in b[]
  )(i = [], x++)            //   initial call to g with a = [], i = 0; increment x
  .length - k ?             //   if the length of the result is not equal to k:
    F(n)                    //     just call F with n unchanged
  :                         //   else:
    [b, ...F(n - 1)]        //     append b[] to the final result and decrement n
:                           // else:
  []                        //   stop recursion