20
\$\begingroup\$

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.

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

20 Answers 20

7
\$\begingroup\$

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~

\$\endgroup\$
  • \$\begingroup\$ This is my original algorithm... The Perl algorithm is better. \$\endgroup\$ – Leaky Nun Sep 15 '17 at 15:09
  • \$\begingroup\$ Very nice. Here it is in 12 bytes \$\endgroup\$ – Jonathan Allan Sep 15 '17 at 15:37
  • \$\begingroup\$ Here's another 12 byter ÆEZ×Ụ’$€$ZÆẸ \$\endgroup\$ – miles Sep 15 '17 at 22:06
  • \$\begingroup\$ This now gives [1,18] for [15,18]. The initial version was returning the correct answer ([5,18]). \$\endgroup\$ – Arnauld Sep 16 '17 at 14:27
  • 1
    \$\begingroup\$ Ah - yes we'd need a filler of zero on the transpose. ÆEz®0iṂ$¦€ZÆẸ should do the trick for 13. \$\endgroup\$ – Jonathan Allan Sep 16 '17 at 15:18
4
\$\begingroup\$

R, 143 139 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 
\$\endgroup\$
  • \$\begingroup\$ ! 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 \$\endgroup\$ – Giuseppe Sep 15 '17 at 13:41
  • 1
    \$\begingroup\$ 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)... \$\endgroup\$ – Giuseppe Sep 15 '17 at 14:06
  • 1
    \$\begingroup\$ Indeed! (though calculating a*b/GCD(a,b) is not shorter than LCM(a,b)). \$\endgroup\$ – plannapus Sep 15 '17 at 14:10
  • \$\begingroup\$ 120 bytes -- anonymous function + literal newline for -3 bytes \$\endgroup\$ – Giuseppe Sep 15 '17 at 14:46
4
\$\begingroup\$

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

Mathematica, 82 bytes

#&@@Select[Subsets[Flatten@Divisors[{t=#,r=#2}],{2}],GCD@@#==1&&LCM@@#==t~LCM~r&]&
\$\endgroup\$
  • \$\begingroup\$ I am not sure, but could you not use list indexing Select[...][[1]] instead of First@Select[...] to save a byte? \$\endgroup\$ – Jonathan Frech Sep 15 '17 at 19:58
  • \$\begingroup\$ yes, but then I could use #&@@ instead of [[1]] to save one more ;-) \$\endgroup\$ – J42161217 Sep 15 '17 at 20:54
3
\$\begingroup\$

JavaScript (ES6), 90 84 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
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

Haskell, 50 48 47 45 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

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

05AB1E, 12 bytes

Ñ`âʒ.¿I.¿Q}н

Try it online! or as a Test suite

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

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.

\$\endgroup\$
2
\$\begingroup\$

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

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

\$\endgroup\$
  • 1
    \$\begingroup\$ u*v`div`gcd u v saves a byte. \$\endgroup\$ – Lynn Sep 15 '17 at 17:16
  • \$\begingroup\$ Is there any reason not to use the built-in lcm function? \$\endgroup\$ – Laikoni Sep 16 '17 at 7:37
  • \$\begingroup\$ Also rem a x+rem b y+gcd x y<2 should work. \$\endgroup\$ – Laikoni Sep 16 '17 at 7:39
  • \$\begingroup\$ @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. \$\endgroup\$ – jferard Sep 16 '17 at 8:31
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – jferard Sep 16 '17 at 9:00
2
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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*

Try it online! or Try the test suite.

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

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

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

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] $_) == [*] $_ }
}
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Golfing in progress... \$\endgroup\$ – Erik the Outgolfer Sep 15 '17 at 14:46
  • \$\begingroup\$ 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) \$\endgroup\$ – Jonathan Frech Sep 19 '17 at 5:05
  • \$\begingroup\$ Just as a question, are you using the + operator in d=+E or c=+(c==z) to convert a boolean into an integer? \$\endgroup\$ – Jonathan Frech Sep 19 '17 at 5:06
  • \$\begingroup\$ @JonathanFrech Yes I am, since you can't use True and False instead of 1 and 0 in sympy. \$\endgroup\$ – Erik the Outgolfer Sep 19 '17 at 10:26
  • \$\begingroup\$ That is the first instance I ever saw where the vanilla +... has any use. \$\endgroup\$ – Jonathan Frech Sep 19 '17 at 10:38
1
\$\begingroup\$

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
    µ           New monadic link
     Ụ€         Grade up each pair (1-indexed)
       ’        Convert to 0-indexing (vectorises)
        ×       Multiply each pair by its grade (vectorises)
         µ      New monadic link
          Z     Zip back into separate lists of prime factor exponents
           ÆẸ   Turn prime exponent lists back into values (vectorises)
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

05AB1E, 32 26 24 22 20 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
\$\endgroup\$
  • \$\begingroup\$ What’s it doing? \$\endgroup\$ – Lynn Sep 15 '17 at 15:15
  • \$\begingroup\$ Same as yours, but by actually factorising and comparing the exponents and recombining the factors. \$\endgroup\$ – Neil Sep 15 '17 at 15:22

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.