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.


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


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


  • 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!
  • 2
    \$\begingroup\$ 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? \$\endgroup\$ May 6, 2020 at 3:34
  • 1
    \$\begingroup\$ @Jonah Removed the mathy stuff, tried making it more concrete. Thank you! \$\endgroup\$ May 6, 2020 at 4:40
  • 2
    \$\begingroup\$ I believe k = 0 should be excluded from the input range, as there is only one possible k-tuple []. \$\endgroup\$
    – Bubbler
    May 6, 2020 at 4:46
  • 2
    \$\begingroup\$ 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? \$\endgroup\$ May 6, 2020 at 9:08
  • 1
    \$\begingroup\$ Suggested test case: k=4, n=2 (or any other with k>n>0). \$\endgroup\$
    – Zgarb
    May 6, 2020 at 14:14

7 Answers 7


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.


Uses the 05AB1E-encoding.


Try it online!


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


∞æ              # 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.
  • 4
    \$\begingroup\$ Hey, Adnan, it's been long! \$\endgroup\$
    – Luis Mendo
    May 6, 2020 at 12:36
  • 2
    \$\begingroup\$ Hey @LuisMendo, it has been a long time indeed! Good to see you ;). \$\endgroup\$
    – Adnan
    May 6, 2020 at 12:46
  • 2
    \$\begingroup\$ Brilliant solution! \$\endgroup\$ May 6, 2020 at 16:35
  • 1
    \$\begingroup\$ Why doesn't ù and £ take existing items on the stack? \$\endgroup\$
    – user92069
    May 7, 2020 at 3:19
  • 3
    \$\begingroup\$ @Λ̸̸ – Mostly shitty programming when I developed the language. \$\endgroup\$
    – Adnan
    May 7, 2020 at 12:46

Husk, 9 bytes


Try it online!


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


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


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


Try it online!


( 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.