18
\$\begingroup\$

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

\$\endgroup\$
  • 4
    \$\begingroup\$ Note: computing LCM[numerators]/GCD[denominators] may not work when the input contains a non-reduced rational number. e.g. 1/3, 2/8. \$\endgroup\$ – JungHwan Min Jun 18 '17 at 2:26
  • \$\begingroup\$ So if I reduce it, it will work? \$\endgroup\$ – Leaky Nun Jun 18 '17 at 2:32
  • \$\begingroup\$ @LeakyNun Yes, it will. \$\endgroup\$ – JungHwan Min Jun 18 '17 at 2:34
  • \$\begingroup\$ 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. \$\endgroup\$ – JungHwan Min Jun 18 '17 at 9:56
  • \$\begingroup\$ What about an LCM built-in being used but only with integers - competing or not? \$\endgroup\$ – Jonathan Allan Jun 18 '17 at 10:09

12 Answers 12

5
\$\begingroup\$

Jelly, 19 bytes

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

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ tfw Jelly sucks with fractions \$\endgroup\$ – Erik the Outgolfer Jun 18 '17 at 8:41
  • 2
    \$\begingroup\$ g/:@$€ -> :g/$€ \$\endgroup\$ – Jonathan Allan Jun 18 '17 at 10:37
  • 2
    \$\begingroup\$ Save another two bytes with: :g/$€ZµḢæl/,Ḣg/$ \$\endgroup\$ – Jonathan Allan Jun 18 '17 at 10:43
  • \$\begingroup\$ @JonathanAllan That's a nice piece of code... \$\endgroup\$ – Erik the Outgolfer Jun 18 '17 at 11:46
6
\$\begingroup\$

J, 3 bytes, non-competing.

*./

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

\$\endgroup\$
4
\$\begingroup\$

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!

\$\endgroup\$
4
\$\begingroup\$

Python 2, 65 bytes (non-competing)

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

Try it online!

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

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.

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

Pari/GP, 3 bytes, non-competing

lcm

Try it online!

\$\endgroup\$
  • \$\begingroup\$ @JungHwanMin Does it mean that a GCD built-in is allowed? \$\endgroup\$ – alephalpha Jun 18 '17 at 10:23
  • \$\begingroup\$ Good point. Yes, as long as its inputs are only integers. \$\endgroup\$ – JungHwan Min Jun 18 '17 at 10:25
2
\$\begingroup\$

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

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.

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

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.

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

Mathematica, 3 bytes, non-competing

LCM

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

\$\endgroup\$
  • 3
    \$\begingroup\$ 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 \$\endgroup\$ – Beta Decay Jun 18 '17 at 9:37
  • \$\begingroup\$ @BetaDecay Yep... So it's non-competing now. \$\endgroup\$ – JungHwan Min Jun 18 '17 at 10:50
1
\$\begingroup\$

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!

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

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))))
\$\endgroup\$

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.