LCM of Rational Numbers

Question

The least common multiple (LCM) of a set of numbers A is the smallest integer b such that b/a is an integer for all integers a in A. This definition can be extended to rational numbers!

Task

Find the smallest positive rational b such that b/a is an integer for all rationals a in the input.

Rules

• Standard loopholes are forbidden.
• You may take numerators and denominators separately in the input, but may not take doubles, floats, etc.
• The input may not be fully reduced.
• You may take integer inputs as rationals with denominator of 1.
• Submissions that would feed rational numbers to an LCM/GCD builtin are allowed, but non-competing.

Test Cases

In:  3
Out: 3

In:  1/17
Out: 1/17

In:  1/2, 3/4
Out: 3/2

In:  1/3, 2/8
Out: 1

In:  1/4, 3
Out: 3

In:  2/5, 3
Out: 6

In:  1/2, 3/4, 5/6, 7/8
Out: 105/2

This is code-golf, so submissions using the fewest bytes win!

Answer 1

Jelly, 19 bytes

g/:@$€Z©Ḣæl/;®Ḣg/$¤

Try it online!

Answer 2

J, 3 bytes, non-competing.

*./

Given a list of rational inputs, this folds LCM through it.

Answer 3

Python 2, 65 bytes (non-competing)

lambda x:reduce(lambda x,y:x*y/gcd(x,y),x)
from fractions import*

Try it online!

Answer 4

sed, 374 (373+1) bytes

^{sed's -E flag counts as one byte. Note: I haven't tried to golf this yet, and probably won't for quite some time.}
Input is taken in unary, and output is in unary. Spaces must surround every fraction. Example: echo " 1/111 111/11111 111111/111 ".

:d;s, (1*)/\1(1*), \1/\22,;s,(1*)(1*)/\2 ,2\1/\2 ,;td;s,1*(1/22*),\1,g;s,(22*/1)1*,\1,g;:r;s,((1*)/1*)2,\1\2,;s,2(1*/(1*)),\2\1,;tr;h;s,1*/,,g;:g;s/^(1*) 1(1*) 1(1*)/1\1 \2 \3/;tg;s/  */ /g;s/^/ /;/1 1/bg;x;s,/1*,,g;s/^( 1*)( 1*)/\1\2\2/;:l;s/^(1*) (1*) \2(1*)/\1\2 \2 \3/;tl;/  $/be;/  /{s/^(1*) 1*  1*( 1*)/ \1\2\2/;bl};s/^(1* 1* )(1*) (1*)/\1\2\3 \3/;bl;:e;G;s, *\n *,/,

Try it online!

Answer 5

Pari/GP, 3 bytes, non-competing

lcm

Try it online!

Answer 6

JavaScript (ES6), 85 bytes

a=>a.reduce(([b,c],[d,e,g=(b,c)=>c?g(c,b%c):b,h=g(b*e,c*d),i=g(b*d,h)])=>[b*d/i,h/i])

Look no builtins! No doubt someone will beat this using a recursive approach or something.

Answer 7

Common Lisp, 154 bytes

(defun f(l &aux(s(pairlis l l)))(loop(and(eval`(=,@(mapcar'car s)))(return(caar s)))(let((x(assoc(reduce'min s :key'car)s)))(rplaca x(+(car x)(cdr x))))))

Algorithm used (specified for integers, but works also for rationals).

First make an associative list of the input data with itself, to get track of the initial values of the elements, so the operating sequence is given by the “car”s of the list.

(defun f(l &aux (s (pairlis l l)))        ; make the associative list
  (loop
     (when (eval `(= ,@(mapcar 'car s))) ; when the car are all equal
       (return (caar s)))                 ; exit with the first one
     (let ((x (assoc (reduce 'min s :key 'car) s))) ; find the (first) least element
       (rplaca x (+ (car x) (cdr x))))))  ; replace its car adding the original value (cdr)

Test cases:

CL-USER> (f '(3))
3
CL-USER> (f '(1/17))
1/17
CL-USER> (f '(1/2 3/4))
3/2
CL-USER> (f '(1/3 2/8))
1
CL-USER> (f '(1/4 3))
3
CL-USER> (f '(2/5 3))
6
CL-USER> (f '(1/2 3/4 5/6 7/8))
105/2

Note: The solution is without the use of the builting lcm and gcd, that accept integers.

Answer 8

Perl 6,  46  42 bytes

{[lcm](@_».numerator)/[gcd] @_».denominator}

test it

{[lcm](($/=@_».nude)[*;0])/[gcd] $/[*;1]}

test it

Input is a list of Rational numbers.

Expanded:

{ # bare block lambda with implicit parameter list ｢@_｣

  [lcm](            # reduce using &infix:<lcm>
    (
      $/ = @_».nude # store in ｢$/｣ a list of the NUmerators and DEnominiators
                    # ((1,2), (3,4))

    )[
      *;            # from all of the first level ｢*｣,
      0             # but only the 0th of the second level (numerators)
    ]
  )
  /
  [gcd] $/[ *; 1 ]  # gcd of the denominators
}

Answer 9

Retina, 117 bytes

\d+
$*
\b(1+)(\1)*/(\1)+\b
$#2$*11/$#3$*
{`^((1+)\2*)/(1+)+ (\2)+/\3+\b
$1 $#4$*1/$3
}`\G1(?=1* (1+))|\G 1+
$1
1+
$.&

Try it online! Takes input as a space-separated series of improper fractions (no integers or mixed numbers). Explanation:

\d+
$*

Converts decimal to unary.

\b(1+)(\1)*/(\1)+\b
$#2$*11/$#3$*

This reduces each fraction to its lowest terms. Capture group 1 represents the GCD of the numerator and denominator, so we count the number of captures before and after the /. \b(1+)+/(\1)+\b doesn't seem to count the number of captures correctly for some reason, so I use an extra capturing group and add 1 to the result.

{`^((1+)\2*)/(1+)+ (\2)+/\3+\b
$1 $#4$*1/$3

This does a number of things. Capture group 2 represents the GCD of the numerators of the first two fractions, while capture group 3 represents the GCD of the denominators. $#4 is therefore the second numerator divided by their GCD. (Again, I couldn't could the number of captures of the first numerator, but I only need to divide one numerator by their GCD, so it doesn't cost me quite so much.)

}`\G1(?=1* (1+))|\G 1+
$1

Now that the second numerator has been divided by their GCD, we just use this expression from the unary arithmetic tutorial to multiply the two together, resulting in the LCM. We then repeat the exercise for any remaining fractions.

1+
$.&

Converts unary back to decimal.

Answer 10

Mathematica, 3 bytes, non-competing

LCM

Mathematica's built-in LCM function is capable of handling rational number inputs.

Answer 11

PHP, 194 bytes

<?for(list($n,$d)=$_GET,$p=array_product($d);$x=$n[+$k];)$r[]=$x*$p/$d[+$k++];for($l=1;$l&&++$i;$l=!$l)foreach($r as$v)$l*=$i%$v<1;for($t=1+$i;$p%--$t||$i%$t;);echo$p/$t>1?$i/$t."/".$p/$t:$i/$t;

-4 Bytes with PHP>=7.1 [$n,$d]=$_GET instead of list($n,$d)=$_GET

Try it online!

Answer 12

Common Lisp, 87 78 bytes

Using lcm and gcd, which have integer inputs:

(defun l(a)(/(apply #'lcm(mapcar #'numerator a))(apply #'gcd(mapcar #'denominator a))))

More golfed:

(defun l(a)(eval`(/(lcm,@(mapcar'numerator a))(gcd,@(mapcar'denominator a))))