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.
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)
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
0 comment threads