14
\$\begingroup\$

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!
\$\endgroup\$
  • \$\begingroup\$ Is "print [1, 1, ...[k-1 ones]..., x] for x in range from 1 to n" valid? \$\endgroup\$ – my pronoun is monicareinstate May 6 at 3:05
  • 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\$ – my pronoun is monicareinstate May 6 at 3:34
  • 1
    \$\begingroup\$ @Jonah Removed the mathy stuff, tried making it more concrete. Thank you! \$\endgroup\$ – bitconfused May 6 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 at 4:46
  • 1
    \$\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\$ – Steve Bennett May 6 at 9:08
7
\$\begingroup\$

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

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]]
| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Charcoal, 58 bytes

NθNη≔⁰ζ⊞υ⟦⟧W‹LΦυ⁼Lκθη«≦⊕ζFΦυ⬤κ⬤…²ζ∨﹪μξ﹪ζξ⊞υ⁺⟦ζ⟧κ»I…Φυ⁼Lιθη

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

NθNη

Input k and n.

≔⁰ζ⊞υ⟦⟧

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

W‹LΦυ⁼Lκθη«

Repeat until we have at least k n-tuples.

≦⊕ζ

Increment the candidate number.

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

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.

»I…Φυ⁼Lιθη

Print the first n k-tuples.

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$

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.