# Generate *all* coprime tuples

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 -> [,,,,]
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!
• I think your comment reduced clarity. Do we have to write a program that can output all possible tuples, or it simply has to produce no repetitions? May 6 '20 at 3:34
• @Jonah Removed the mathy stuff, tried making it more concrete. Thank you! May 6 '20 at 4:40
• I believe k = 0 should be excluded from the input range, as there is only one possible k-tuple []. May 6 '20 at 4:46
• I think maybe the first sentence is saying that it's the "first n tuples", but the order can be specified by the submission - as long as it can guarantee that a given tuple will eventually appear for some finite n? May 6 '20 at 9:08
• Suggested test case: k=4, n=2 (or any other with k>n>0). May 6 '20 at 14:14

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

• Hey, Adnan, it's been long! May 6 '20 at 12:36
• Hey @LuisMendo, it has been a long time indeed! Good to see you ;). May 6 '20 at 12:46
• Brilliant solution! May 6 '20 at 16:35
• Why doesn't ù and £ take existing items on the stack?
– user92069
May 7 '20 at 3:19
• @Λ̸̸ – Mostly shitty programming when I developed the language. May 7 '20 at 12:46

# 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]]


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

# 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!

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

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

# 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