# LCM of Rational Numbers

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!

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 , so submissions using the fewest bytes win!

• Note: computing LCM[numerators]/GCD[denominators] may not work when the input contains a non-reduced rational number. e.g. 1/3, 2/8. Jun 18, 2017 at 2:26
• So if I reduce it, it will work? Jun 18, 2017 at 2:32
• @LeakyNun Yes, it will. Jun 18, 2017 at 2:34
• To encourage people to submit non-builtin answers, I've edited the question, making builtin answers non-competing (still allowed). If this is a problem, I will rollback my edit. Jun 18, 2017 at 9:56
• What about an LCM built-in being used but only with integers - competing or not? Jun 18, 2017 at 10:09

# J, 3 bytes

*./


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

# Jelly, 19 bytes

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


Try it online!

• tfw Jelly sucks with fractions Jun 18, 2017 at 8:41
• g/:@$€ -> :g/$€ Jun 18, 2017 at 10:37
• Save another two bytes with: :g/$€ZµḢæl/,Ḣg/$ Jun 18, 2017 at 10:43
• @JonathanAllan That's a nice piece of code... Jun 18, 2017 at 11:46

# Jelly, 12 bytes

:g/æl/;g/}ɗ/


Try it online!

Takes input as [[list of numerators], [list of denominators]]. +2 bytes to take input as a list of [numerator, denominator] pairs

## How it works

:g/æl/;g/}ɗ/ - Main link. Takes a pair of lists [N, D] on the left
/          - Columnwise reduce by:
g           -   GCD
:            - Divide, reducing the fractions to their simplest form
ɗ  - Group the previous 3 links into a dyad f(N, D):
æl/       -   LCM of N
}   -   To D:
g/    -     GCD
;      -   Concatenate
/ - Reduce; Yield f(N, D) where N is the first list and D the second


The 14 byte version transposes the input with Z to get it into the [N, D] format, then uses $ as a "grouping" construct the make the :g/ act on that # 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!

# Python 2, 65 bytes

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


Try it online!

## 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.

# Pari/GP, 30 bytes

This only apply the lcm built-in on integers.

a->d=denominator(a);lcm(a*d)/d


Try it online!

# Pari/GP, 3 bytes

This feeds rational numbers to the lcm built-in, so it is non-competing.

lcm


Try it online!

• @JungHwanMin Does it mean that a GCD built-in is allowed? Jun 18, 2017 at 10:23
• Good point. Yes, as long as its inputs are only integers. Jun 18, 2017 at 10:25

# 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 }  # 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.

# 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.

• W00t? Try this at your REPL (/ (lcm 1 3 5 7) (gcd 2 4 6 8)).
– Kaz
Jun 19, 2017 at 14:24
• @Kaz, since, as it said in problem, “Submissions that would feed rational numbers to an LCM/GCD builtin are allowed, but non-competing”. Jun 19, 2017 at 14:27
• In Lisp terms, strictly speaking, we are in fact feeding rationals when we call (lcm 1 3 5 7), since integers are a subtype of rationals, but I think the rule is supposed to exclude use of a lcm or gcd which allows rational inputs.
– Kaz
Jun 19, 2017 at 14:34
• @Kaz, ops... I misinterpreted the rules! Should I remove the post? (maybe it is not good marketing for Common Lisp :) Jun 19, 2017 at 14:52
• I'd just put in a note that this is a solution without using the built-in integer lcm and gcd.
– Kaz
Jun 19, 2017 at 14:55

# 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!

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


# Mathematica, 3 bytes

LCM


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

• While answering your own question is fine, I don't think it's very sporting to answer it with a solution that has a very real chance of winning :P Jun 18, 2017 at 9:37
• @BetaDecay Yep... So it's non-competing now. Jun 18, 2017 at 10:50