Borromean coprimes
Given 3 positive integers, indicate whether they are Borromean coprimes.
Definition
3 positive integers are called Borromean coprimes if both of the following are true:
- Their greatest common divisor is 1.
- The greatest common divisor of every pair is greater than 1.
In summary, the triple of integers is coprime, but removing any single integer leaves a pair of integers that are not coprime. The name is by analogy with Borromean rings.
Input
- 3 positive integers.
- This may be as 3 separate inputs, or any ordered data structure.
- Your code must work for integers in any order (you must not assume that they are sorted).
- Your code must support input integers up to and including 127.
Output
- 1 of 2 distinct values to represent "True" and "False".
Examples
GCD not equal to 1 for the triple
- Input:
2, 4, 6 - Output:
False
The greatest common divisor of the triple is 2, so these are not Borromean coprimes.
GCD equal to 1 for a pair
- Input:
2, 3, 5 - Output:
False
The greatest common divisor of the pair 2, 3 is 1, so these are not Borromean coprimes.
Borromean coprimes
- Input:
6, 10, 15 - Output:
True
The greatest common divisors of each pair are:
- GCD(6, 10) = 2
- GCD(6, 15) = 3
- GCD(10, 15) = 5
The greatest common divisor of the triple is 1, and the greatest common divisor of every pair is greater than 1, so these are Borromean coprimes.
Non-golfed example code
Here is some Python code that meets the requirements of this challenge. The function borromean_coprimes returns True or False.
from math import gcd
def borromean_coprimes(x, y, z):
return (
coprime_triple(x, y, z)
and not coprime(x, y)
and not coprime(x, z)
and not coprime(y, z)
)
def coprime(x, y):
return gcd(x, y) == 1
def coprime_triple(x, y, z):
return gcd(x, y, z) == 1
Test cases
Test cases are in the format comma, separated, inputs : "output".
You may use any 2 distinct values instead of "True" and "False".
1, 1, 1 : "False"
1, 1, 2 : "False"
1, 1, 3 : "False"
1, 2, 2 : "False"
1, 2, 3 : "False"
2, 2, 2 : "False"
2, 2, 3 : "False"
2, 3, 3 : "False"
2, 3, 4 : "False"
2, 3, 5 : "False"
2, 4, 5 : "False"
2, 4, 6 : "False"
127, 127, 127: "False"
18, 33, 88 : "True"
108, 20, 105 : "True"
98, 30, 105 : "True"
22, 36, 33 : "True"
82, 30, 123 : "True"
40, 55, 22 : "True"
45, 12, 10 : "True"
38, 57, 78 : "True"
35, 84, 80 : "True"
84, 33, 22 : "True"
105, 54, 80 : "True"
26, 96, 39 : "True"
18, 26, 117 : "True"
50, 75, 48 : "True"
95, 76, 70 : "True"
50, 96, 45 : "True"
85, 34, 40 : "True"
84, 104, 39 : "True"
45, 72, 110 : "True"
72, 68, 51 : "True"
20, 105, 28 : "True"
75, 102, 100 : "True"
90, 105, 14 : "True"
105, 110, 84 : "True"
78, 70, 21 : "True"
105, 96, 14 : "True"
110, 120, 33 : "True"
70, 84, 15 : "True"
50, 6, 105 : "True"
70, 21, 45 : "True"
48, 70, 21 : "True"
76, 18, 57 : "True"
126, 77, 66 : "True"
6, 88, 99 : "True"
33, 77, 126 : "True"
88, 72, 33 : "True"
12, 63, 56 : "True"
80, 36, 105 : "True"
35, 110, 77 : "True"
21, 14, 18 : "True"
68, 85, 70 : "True"
75, 108, 80 : "True"
18, 21, 98 : "True"
26, 36, 39 : "True"
30, 98, 21 : "True"
50, 15, 36 : "True"
78, 51, 34 : "True"
44, 98, 77 : "True"
114, 105, 80 : "True"
15, 10, 72 : "True"
5, 91, 18 : "False"
51, 41, 98 : "False"
66, 78, 20 : "False"
76, 18, 50 : "False"
124, 105, 50 : "False"
54, 1, 93 : "False"
60, 41, 104 : "False"
127, 62, 40 : "False"
112, 101, 122 : "False"
7, 12, 74 : "False"
18, 95, 71 : "False"
123, 74, 3 : "False"
51, 79, 7 : "False"
9, 67, 98 : "False"
37, 6, 90 : "False"
43, 1, 45 : "False"
36, 14, 44 : "False"
37, 1, 111 : "False"
55, 89, 26 : "False"
90, 53, 28 : "False"
83, 12, 31 : "False"
19, 112, 5 : "False"
92, 19, 99 : "False"
58, 59, 124 : "False"
9, 106, 85 : "False"
108, 108, 6 : "False"
69, 31, 76 : "False"
96, 6, 42 : "False"
105, 47, 90 : "False"
43, 22, 29 : "False"
113, 19, 73 : "False"
77, 103, 113 : "False"
91, 89, 17 : "False"
60, 16, 61 : "False"
44, 87, 115 : "False"
28, 80, 108 : "False"
11, 116, 76 : "False"
105, 79, 95 : "False"
62, 80, 80 : "False"
7, 60, 104 : "False"
91, 106, 34 : "False"
125, 105, 56 : "False"
9, 74, 87 : "False"
88, 68, 6 : "False"
40, 17, 109 : "False"
116, 83, 29 : "False"
102, 32, 110 : "False"
121, 20, 85 : "False"
112, 44, 121 : "False"
74, 102, 39 : "False"
Scoring
This is a code golf challenge. Your score is the number of bytes in your code.
Explanations are optional, but I'm more likely to upvote answers that have one.
2 answers
You are accessing this answer with a direct link, so it's being shown above all other answers regardless of its score. You can return to the normal view.
Jelly, 10 bytes
ṭŒcg/€ċ1=1
A monadic link taking a list of three positive integers and returning 1 if they are Borromean coprimes and 0 if not. TIO link checks all of the test cases.
Explanation
ṭŒc | Tag original list onto list of combinations of length 2
g/€ | Reduce each list using GCD
ċ1 | Count 1s
=1 | = 1
SageMath, 68 66 64 Byte. 62 if you don't count the m=
g=gcd;m=lambda a,b,c:min(g(a,b),g(a,c),g(b,c))<2or g(g(b,c),a)>1
Returns False for borromean coprimes and True for all other natural numbers >1. Use it like this m(6,10,15).
Using min to get the lowest gcd of all pairs. It is shorter than comparing each to 1 or 2. When 1 pairs gcd is 1, the minimal value is also 1 and it isn't a borromean coprime. Sadly, SageMath gcd() doesn't support more than 2 arguments, unlike regular python, so 2 nested gcd calls are need to test if the total gcd is 1.
There is probably a much shorter solution.
You can test it here: https://sagecell.sagemath.org/ But you have to copy-paste the code.
Older version:
Didn't mix True and False:
g=gcd;m=lambda a,b,c:(min(g(a,b),g(a,c),g(b,c))>1)&(g(g(b,c),a)<2)
m=lambda a,b,c:min(gcd(a,b),gcd(a,c),gcd(b,c))<2|(gcd(gcd(b,c),a)>1)
0 comment threads