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!

• JungHwan Min: Note: computing LCM[numerators]/GCD[denominators] may not work when the input contains a non-reduced rational number. e.g. 1/3, 2/8.
• Leaky Nun: So if I reduce it, it will work?
• JungHwan Min: @LeakyNun Yes, it will.
• JungHwan Min: 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.
• Jonathan Allan: What about an LCM built-in being used but only with integers - competing or not?

Answer 1

J, 3 bytes

*./

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

Answer 2

Jelly, 19 bytes

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

Try it online!

• Erik the Outgolfer: tfw Jelly sucks with fractions
• Jonathan Allan: g/:@$€ -> :g/$€
• Jonathan Allan: Save another two bytes with: :g/$€ZµḢæl/,Ḣg/$
• Erik the Outgolfer: @JonathanAllan That's a nice piece of code...

Answer 3

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

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円 ,21円/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*)/11円 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

Python 2, 65 bytes

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

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

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!

• alephalpha: @JungHwanMin Does it mean that a GCD built-in is allowed?
• JungHwan Min: Good point. Yes, as long as its inputs are only 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.

• Neil: There's a better way of doing GCD which would save two bytes but this post predates the Retina 0.8.2/1 split so it would be confusing to edit it.

Answer 10

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.

• Kaz: W00t? Try this at your REPL (/ (lcm 1 3 5 7) (gcd 2 4 6 8)).
• Renzo: @Kaz, since, as it said in problem, "Submissions that would feed rational numbers to an LCM/GCD builtin are allowed, but non-competing".
• Kaz: 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.
• Renzo: @Kaz, ops... I misinterpreted the rules! Should I remove the post? (maybe it is not good marketing for Common Lisp :)
• Kaz: I'd just put in a note that this is a solution without using the built-in integer lcm and gcd.

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

Answer 13

Mathematica, 3 bytes

LCM

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

• Beta Decay: 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
• JungHwan Min: @BetaDecay Yep... So it's non-competing now.