# Make two numbers co-prime while preserving their least common multiple

Given two positive integers a and b, output two positive integers c and d such that:

• c divides a
• d divides b
• c and d are co-prime
• the least common multiple of c and d equals the least common multiple of a and b.

If there are more than one possible answers, you can output only one or all of them.

Test cases:

 a  b  c  d
12 18  4  9
18 12  9  4
5  7  5  7
3  6  1  6 or 3 2
9  9  9  1 or 1 9
6 15  2 15 or 6 5
1  1  1  1


This is . Shortest answer in bytes wins.

• What's to stop me returning (1, LCM)? – Neil Sep 15 '17 at 13:07
• @Neil The requirement that d divides b – Leaky Nun Sep 15 '17 at 13:07
• Maybe you should define LCM or at least not use the acronym. I didn't know what was being asked for a bit. – Ad Hoc Garf Hunter Sep 15 '17 at 13:17

# Jelly, 21 13 bytes

ÆEz®0iṂ$¦€ZÆẸ  Try it online! If a = 2A · 3B · 5C · … and b = 2α · 3β · 5γ · …, then we compute • c = 2A>α?A:0 · 3B>β?B:0 · 5C>γ?C:0 · … • d = 2A>α?0:α · 3B>β?0:β · 5C>γ?0:γ · … Now lcm(c, d) = 2max(A>α?A:0, A>α?0:α) · … = 2max(A, α) · 3max(B, β) · … = lcm(a, b) and gcd(c, d) = 2min(A>α?A:0, A>α?0:α) · … = 20 · 30 · 50 · … = 1. In other words: start from (c, d) = (a, b). Then, for each prime, divide that prime all the way out of the factorization of either c or d: whichever has the smallest exponent for that prime. (In this implementation, in case of a tie, c loses its exponent.) So if a = 2250 = 21 · 32 · 53 and b = 360 = 23 · 32 · 51, then c = 20 · 30 · 53 = 125 and d = 23 · 32 · 50 = 72. Jonathan Allan golfed down a whopping 8 bytes! Thank you~ • This is my original algorithm... The Perl algorithm is better. – Leaky Nun Sep 15 '17 at 15:09 • Very nice. Here it is in 12 bytes – Jonathan Allan Sep 15 '17 at 15:37 • Here's another 12 byter ÆEZ×Ụ’$€$ZÆẸ – miles Sep 15 '17 at 22:06 • This now gives [1,18] for [15,18]. The initial version was returning the correct answer ([5,18]). – Arnauld Sep 16 '17 at 14:27 • Ah - yes we'd need a filler of zero on the transpose. ÆEz®0iṂ$¦€ZÆẸ should do the trick for 13. – Jonathan Allan Sep 16 '17 at 15:18

# R, 143139 123 bytes

f=function(a,b,q=1:(a*b))for(i in 1:a)for(j in 1:b)if(!a%%i+b%%j&max(q[!i%%q+j%%q])<2&i*j==min(q[!q%%a+q%%b]))cat(i,j,"\n")


(Thanks to @Giuseppe for those 19 bytes off!)

With indentations, newlines and some explanations:

f=function(a,b,
q=1:(a*b)) #Defined as function arguments defaults to avoid having to use curly brackets
for(i in 1:a)
for(j in 1:b)
if(!a%%i + b%%j & #Is a divided by c and b divided by d
max(q[!i%%q+j%%q])<2 & #Are c and d coprimes
i*j==min(q[!q%%a+q%%b])) #Is this the same lcm
cat(i,j,"\n") #Then print


Test cases:

> f=function(a,b,q=1:(a*b))for(i in 1:a)for(j in 1:b)if(!a%%i+b%%j&max(q[!i%%q+j%%q])<2&i*j==min(q[!q%%a+q%%b]))cat(i,j,"\n")
> f(5,7)
5 7
> f(12,18)
4 9
> f(6,15)
2 15
6 5
> f(1,1)
1 1

• ! has higher precedence than & and | but lower than + and *; you should be able to golf down a few bytes that way; i.e., !i%%q&j%%q should be equivalent to !i%%q+j%%q – Giuseppe Sep 15 '17 at 13:41
• Okay well observation: if GCD(c,d)==1, then LCM(c,d)==c*d. So we can test GCD(c,d)==1 and then check if c*d==a*b/GCD(a,b) since the latter is LCM(a,b)... – Giuseppe Sep 15 '17 at 14:06
• Indeed! (though calculating a*b/GCD(a,b) is not shorter than LCM(a,b)). – plannapus Sep 15 '17 at 14:10
• 120 bytes -- anonymous function + literal newline for -3 bytes – Giuseppe Sep 15 '17 at 14:46

# Husk, 10 bytes

→ÖF§-⌋⌉ΠmḊ


Brute force. Takes and returns lists, and works for more than two numbers too. Try it online!

## Explanation

→ÖF§-⌋⌉ΠmḊ  Implicit input, say [6,15]
mḊ  Map divisors: [[1,2,3,6],[1,3,5,15]]
Π    Cartesian product:[[1,1],[2,1],[1,3],[2,3],[3,1],[1,5],[3,3],[6,1],[1,15],[2,5],[3,5],[6,3],[2,15],[6,5],[3,15],[6,15]]
Ö          Sort by
F         reduce by
⌉      lcm
-⌋       minus gcd: [[1,1],[3,3],[2,1],[1,3],[3,1],[6,3],[1,5],[2,3],[6,1],[2,5],[3,15],[1,15],[3,5],[6,15],[2,15],[6,5]]
→           Get last element: [6,5]


# Mathematica, 82 bytes

#&@@Select[Subsets[Flatten@Divisors[{t=#,r=#2}],{2}],GCD@@#==1&&LCM@@#==t~LCM~r&]&

• I am not sure, but could you not use list indexing Select[...][[1]] instead of First@Select[...] to save a byte? – Jonathan Frech Sep 15 '17 at 19:58
• yes, but then I could use #&@@ instead of [[1]] to save one more ;-) – J42161217 Sep 15 '17 at 20:54

# JavaScript (ES6), 9084 80 bytes

Takes input in currying syntax (a)(b) and returns an array of 2 integers.

a=>g=(b,c=1)=>(G=(a,b)=>b?G(b,a%b):a)(c,d=a*b/G(a,b)/c)-1|a%c|b%d?g(b,c+1):[c,d]


### Test cases

let f =

a=>g=(b,c=1)=>(G=(a,b)=>b?G(b,a%b):a)(c,d=a*b/G(a,b)/c)-1|a%c|b%d?g(b,c+1):[c,d]

console.log(JSON.stringify(f(12)(18))) // [ 4,  9 ]
console.log(JSON.stringify(f(18)(12))) // [ 9,  4 ]
console.log(JSON.stringify(f( 5)( 7))) // [ 5,  7 ]
console.log(JSON.stringify(f( 3)( 6))) // [ 1,  6 ] or [ 3, 2 ]
console.log(JSON.stringify(f( 9)( 9))) // [ 9,  1 ] or [ 1, 9 ]
console.log(JSON.stringify(f( 6)(15))) // [ 2, 15 ] or [ 6, 5 ]
console.log(JSON.stringify(f( 1)( 1))) // [ 1,  1 ]

### How?

a =>                            // a = first input
g = (                         // g = recursive function that takes:
b,                          //   b = second input
c = 1                       //   c = first output divisor, initially set to 1
) =>                          //
(G = (a, b) =>              // G = function that takes a and b
b ? G(b, a % b) : a       //     and returns the greatest common divisor
)(                          // we call it with:
c,                        //   - c
d = a * b / G(a, b) / c   //   - d = LCM(a, b) / c = a * b / GCD(a, b) / c
) - 1 |                     // if the result is not 1 (i.e. c and d are not coprime)
a % c |                     // or c does not divide a
b % d ?                     // or d does not divide b:
g(b, c + 1)               //   do a recursive call with c + 1
:                           // else:
[c, d]                    //   return [c, d], a valid factorization of the LCM


# MATL, 17 16 bytes

&YFt&X>2:!=*^!Xp


Try it online!

Same method as Lynn's Jelly solution

It's been a while since I've used any MATL (or matlab for that matter) so many improvements are likely possible.

# Haskell, 50484745 42 bytes

(?)=gcd;a!b|c<-div a$a?b=(c*c?b,div b$c?b)


Idea: I noticed that c*d = a*b/gcd(a,b). So the algorithm performs two steps:

1. Begin with c' = a/gcd(a,b) and d' = b. This fulfils all requirements except that c' and d' have to be co-prime.
2. To make them co-prime, I calculate e = gcd(c',d') and then set c = c'*e and d = d'/e. This keeps all properties (since the combined factors stay the same), but since I remove all shared factors from d, I make cand d coprime.

In my implementation, c' is just called c.

Try it online!

-3 bytes thanks to Laikoni

• Using a pattern guard to bind c saves 3 bytes: Try it online! – Laikoni Oct 25 '17 at 7:40
• @Laikoni Ooh, I didn't even know that trick. Thanks! – Sacchan Oct 25 '17 at 17:56

# 05AB1E, 12 bytes

Ñâʒ.¿I.¿Q}н


Try it online! or as a Test suite

• Still a brute-force :c – Leaky Nun Sep 15 '17 at 13:43
• @LeakyNun: Yeah, there's probably a mathier way to do this :) – Emigna Sep 15 '17 at 13:45

# R, 126 bytes

function(a,b,g=function(x,y)ifelse(o<-x%%y,g(y,o),y),l=a*b/g(a,b))matrix(c(C<-(1:l)[!l%%1:l],D<-l/C),,2)[g(C,D)<2&!a%%C+b%%D,]


Try it online!

This takes a different (and apparently less golfy) approach to finding the values than the other R answer.

Explanation:

function(a,b){
G <- function(x,y)ifelse(o<-x%%y,G(y,o),y) #gcd function, vectorized for x,y
l <- a*b/g(a,b)                            #lcm of a,b
C <- (1:l)[!l%%1:l]                        #divisors of l
D <- l/C                                   #l/C is the other half of the pair
rel_prime <- G(C, D) < 2                   #pairs where C,D are relatively prime, lol, GCD
a_div <- !a%%C                             #divisors of a
b_div <- !b%%D                             #divisors of b
C <- C[rel_prime & a_div & b_div]
D <- D[rel_prime & a_div & b_div]          #filter out the bad pairs
matrix(c(C,D),,ncol = 2)                   #matrix of pairs, returned
}


except I shoehorn all the definitions as default arguments and do all the calculations on one line for the golfiness.

# J, 19 bytes

(*/:"1)&.|:&.(_&q:)


Try it online!

Based on @Lynn's solution.

## Explanation

(*/:"1)&.|:&.(_&q:)  Input: [a, b]
_&q:   Get exponenets of each prime
|:&         Transpose
/:"1 &             Grade each row
*                   Multiply elementwise
&.|:          Transpose
&. _&q:   Convert exponents back to numbers


# Haskell, 91 74 bytes

a!b=[(x,y)|x<-[1..a],y<-[1..b],rem a x+rem b y+gcd x y<2,lcm a b==lcm x y]


Try it online!

Saved 17 bytes thanks to Laikoni

• u*vdivgcd u v saves a byte. – Lynn Sep 15 '17 at 17:16
• Is there any reason not to use the built-in lcm function? – Laikoni Sep 16 '17 at 7:37
• Also rem a x+rem b y+gcd x y<2 should work. – Laikoni Sep 16 '17 at 7:39
• @Laikoni a very good reason: I didn't even know the builtin lcm existed. rem a x+rem b y+gcd x y<2 works, and I wonder if rem a x+rem b y+gcd x y+lcm a b-lcm x y<2 works. There is maybe a (mathematical) guarantee that lcm a b>=lcm x y. – jferard Sep 16 '17 at 8:31
• Indeed, lcm a b>=lcm x y because 1. x=x1*...*xi (prime decomposition), y=y1*...yj, lcm x y=z1*...*zk where z1,...,zk are common to x1,...,xi and y1,...,yj. 2. a=u1*...*um*x1*...*xi (prime decomposition), b=v1*...vn*y1*...yj, lcm a b=t1*...*tl where t1,...,tl are common to u1*...*um*x1*...*xi and v1*...vn*y1*...yj. It's obvious that t1,...,tl contains z1,...,zk, thus lcm a b>=lcm x y. But that's not useful for writing the condition as a sum. – jferard Sep 16 '17 at 9:00

# Python 2, 75 bytes

def f(x):n=1;exec'n+=1;j=k=1\nwhile x[j]%k<1:k*=n**j;j^=1\nx[j]/=k/n;'*x[0]


Input is taken as a list, which the function modifies in place.

Try it online!

# Python 3, 129 bytes

lambda a,b:[[c,d]for c in range(1,-~a)for d in range(1,-~b)if((gcd(c,d)<2)*a*b/gcd(a,b)==c*d/gcd(c,d))>a%c+b%d]
from math import*


Outputs all possible combinations in the form of a nested list.

• You and your bitwise stuff... -~a and -~b can just be rewritten as a+1 and b+1 for readability :P – Stephen Sep 15 '17 at 12:53
• @Stephen As you can see, I specialize in obfuscation – Mr. Xcoder Sep 15 '17 at 12:58
• Doesn't work for my newly added second testcase. – Leaky Nun Sep 15 '17 at 13:30
• @LeakyNun Rolled back. Didn't have time to check the validity of the golf. – Mr. Xcoder Sep 15 '17 at 13:32

# Jelly,  19 15  14 bytes

-4 with pointer from Leaky Nun (use divisor built-in)

I am almost 100% certain this is not the way to actually do this one, but here is a first attempt.
Let's see who outgolfs it with a seven or eight byter!
Yep... see Lynn's answer with explanation!

g/÷æl/
ÆDp/ÇÐṂ


A monadic link taking a list of the two numbers and returning a list of lists of the possibilities.

Try it online!

### How?

g/÷æl/  - Link: gcd divided by lcm: list [x, y]
g/      - reduce by gcd = gcd(x, y)
æl/  - reduce by lcm = lcm(x,y)
÷     - divide

ÆDp/ÇÐṂ - Main link: list [a, b]    e.g. [160, 90]
ÆD      - divisors (vectorises)          [[1,2,4,5,8,10,16,20,32,40,80,160],[1,2,3,5,6,9,10,15,18,30,45,90]]
p/    - reduce by Cartesian product    [[1,1],[1,2],...,[1,90],[2,1],[2,2],...,[2,90],....,[160,90]]
ÐṂ - entries for which this is minimal:
Ç   -   call the last link (1) as a monad

• Let's see who outgolfs it with a seven or eight byter! - Don't think so... – Mr. Xcoder Sep 15 '17 at 13:21
• You think six? ...FIVE?! – Jonathan Allan Sep 15 '17 at 13:21
• :P No... I don't think less than ~13-15 is possible (Dennis would disagree, of course!) – Mr. Xcoder Sep 15 '17 at 13:22
• Divisor built-in? – Leaky Nun Sep 15 '17 at 13:23
• Yeah ÆD but (shrug) brain obviously not in gear... – Jonathan Allan Sep 15 '17 at 13:24

# Perl 6, 72 bytes

{([X] map {grep $_%%*,1..$_},@^a).grep:{([lcm] @a)==([lcm] $_)==[*]$_}}


Try it online!

Takes a list (a, b). Returns a list of all possible lists (c, d).

Explanation:

-> @ab {
# Generate all pairs (c, d)
([X]
# where c divides a and d divides b.
map { grep $_%%*, 1..$_ }, @ab)
# Only keep pairs with lcm(a, b) = lcm(c, d) and lcm(c, d) = c * d.
# The latter implies gcd(c, d) = 1.
.grep: { ([lcm] @ab) == ([lcm] $_) == [*]$_ }
}


# Python 2, 126 121 bytes

def f(a,b):
c=[1,1];p=2
while p<=a*b:
t=m=1
while(a*b)%p<1:m*=p;t=b%p<1;a/=p**(a%p<1);b/=p**t
p+=1;c[t]*=m
return c


Try it online!

# Python 2 + sympy, 148 bytes

from sympy import*
a,b=input()
c=d=z=1
while(a/c*c+b/d*d<a+b)+gcd(c,d)-1+(lcm(c,d)!=lcm(a,b)):E=c==d==z;Q=c==z;d=+E or Q+d;c=+Q or-~c;z+=E
print c,d


Try it online!

-1 thanks to Jonathan Frech.

This answer works in Python 2 (not Python 3), using sympy.gcd and sympy.lcm instead of math.gcd and math.lcm which are only available in Python 3. And yes, this is brute force :)

• Golfing in progress... – Erik the Outgolfer Sep 15 '17 at 14:46
• You may be able to save a byte by defining Q=c==z; (+7 bytes) at the start of the while loop and replacing or(c==z)+d with or Q+d (-4 bytes) and c=+(c==z)or with c=+Q or (-4 bytes). (TIO) – Jonathan Frech Sep 19 '17 at 5:05
• Just as a question, are you using the + operator in d=+E or c=+(c==z) to convert a boolean into an integer? – Jonathan Frech Sep 19 '17 at 5:06
• @JonathanFrech Yes I am, since you can't use True and False instead of 1 and 0 in sympy. – Erik the Outgolfer Sep 19 '17 at 10:26
• That is the first instance I ever saw where the vanilla +... has any use. – Jonathan Frech Sep 19 '17 at 10:38

# Jelly, 13 bytes

Ụ€’×
ÆEz0ÇZÆẸ


Try it online! My first Jelly answer! Edit: ÆEz0µỤ€’×µZÆẸ also works for 13 bytes. Explanation:

ÆE              Get prime factor exponents of both values (vectorises)
z0            Zip but fill the shorter array with 0
Ụ€         Grade up each pair (1-indexed)
’        Convert to 0-indexing (vectorises)
×       Multiply each pair by its grade (vectorises)
Z     Zip back into separate lists of prime factor exponents
ÆẸ   Turn prime exponent lists back into values (vectorises)


# PARI/GP, 86 bytes

This just does what Lynn says in her answer:

f(a,b)=forprime(p=2,a*b,v=valuation(a,p);w=valuation(b,p);if(w<v,b/=p^w,a/=p^v));[a,b]


If I do not count the f(a,b)= part, it is 79 bytes.

# 05AB1E, 3226242220 19 bytes

Ó0ζεD›0sǝ}øεā<ØsmP


Try it online! I still have no idea how to write in this language, but at least it's not a brute-force algorithm. Explanation:

Ó                       Get exponents of prime factors (vectorised)
0ζ                     Zip, filling with 0
ε      }             For each prime
D                  Extract the pair of exponents
›0sǝ              Overwrite the smaller with 0
ø            Zip back into two lists of prime exponents
ε           For each list (} implied)
ā<Ø        Get a list of primes
sm      Raise each prime to the exponent
P     Take the product
`
• What’s it doing? – Lynn Sep 15 '17 at 15:15
• Same as yours, but by actually factorising and comparing the exponents and recombining the factors. – Neil Sep 15 '17 at 15:22