10
$\begingroup$

"CodeGolf" challenge: write the shortest practical Least Common Multiple function that:

  1. Does not use built in GCD, LCM or any related fuctions
  2. Accepts multiple arguments in any order, e.g. LCM[3, 20, 6]
  3. In the spirit of the original, obfuscated is better
$\endgroup$
3
  • $\begingroup$ There were some discussions in the chat room that felt against code golf questions. Hmm... $\endgroup$ – J. M.'s ennui Jan 25 '12 at 22:09
  • $\begingroup$ @J.M. I missed them. If you've got a link I'll read them. $\endgroup$ – Mr.Wizard Jan 25 '12 at 22:28
  • $\begingroup$ Apparently, it's in meta already. Never mind, then... $\endgroup$ – J. M.'s ennui Jan 25 '12 at 22:35
10
$\begingroup$

I am not sure how this compares in terms of length but it does not throw errors and isn't even obfuscated:

lcm[ls__] := 
 Fold[Denominator[Together[Unique[x]/#1 + Unique[x]/#2]] &, 
  First[{ls}], Rest[{ls}]

Just to check it works:

f = RandomInteger[{1, 100}, 200];

lcm @@ f == LCM @@ f
True
$\endgroup$
3
  • $\begingroup$ Thanks for answering. To format your code, select it and click the curly-brackets button above the text box. $\endgroup$ – Mr.Wizard Jan 25 '12 at 21:57
  • $\begingroup$ Yes, I did just that but as you beat me to it it wouldn't let me save my edits ;-) Come to think of it, I am not even sure if using addition of fractions violates the condition about not using "related functions"... $\endgroup$ – Andrzej Kozlowski Jan 25 '12 at 22:02
  • $\begingroup$ Good enough for me. :-) $\endgroup$ – Mr.Wizard Jan 25 '12 at 22:07
10
$\begingroup$

New code, Golfing Simon's method (now v10-syntax compatible):

lcm = Fold[#/#2/._~_~x_|_:># x&,1,{##}]&

This was my original code from a tongue-in-cheek answer on StackOverflow:

gcd = If[#2==0,#,#2~#0~Mod@##]&
lcm = Fold[##/gcd@##&,#,{##2}]&

As a one-liner:

lcm = Fold[If[#2==0,#,#2~#0~Mod@##]&@##^-1##&,#,{##}]&

Intentionally obfuscated:

lcm = If[{}!={##2},#0[If[#2==0,#,#2~#0~Mod@##]&[#,#2]^-1#*#2,##3],#]&

The fact that it throws errors yet works just fine is part of the game.

$\endgroup$
4
  • $\begingroup$ Outstanding! It never occurred to me that you could deal with Rationals and Integers in a single rule. Brilliant stuff. I had a look to see if I could replace Fold with some #0 trickery, but the code to terminate the recursion is just too big. If only Fold was a longer word :-) I think this might just be unbeatable. $\endgroup$ – Simon Woods Jul 14 '12 at 12:20
  • $\begingroup$ @Simon Thanks. :-) Using | on the LHS of a pattern is one of my favorite "tricks." I too experimented with using #0 in place of Fold: that is my "Intentionally obfuscated" line at the end of my answer. By the way, if you use my Fold modification you can knock a couple of characters off of this code. $\endgroup$ – Mr.Wizard Jul 14 '12 at 18:12
  • 1
    $\begingroup$ @Mr.Wizard While musing these fine examples, I figured I couldn't run the first line of your beautiful solution, as now we have associations and #x results in errors. The problem is solved by inserting a space between them. $\endgroup$ – Stitch Jan 23 '17 at 18:43
  • $\begingroup$ @Stitch Thanks; fixed now. $\endgroup$ – Mr.Wizard Jun 14 '17 at 23:55
6
$\begingroup$

I couldn't resist having a go. This is pretty small:

lcm = Fold[#(#/#2/.{_~_~x_:>x,_->1})&,1,{##}]&
$\endgroup$
2
  • $\begingroup$ Marvelous! Just what I was hoping for. Thanks for playing, Simon. I do like your style. :-) $\endgroup$ – Mr.Wizard Jul 13 '12 at 22:48
  • $\begingroup$ Simon, I Accepted this answer for a short while, but seeing as I was able to shorten it significantly lifted the Accept. See if you can again beat me. $\endgroup$ – Mr.Wizard Jul 14 '12 at 0:31

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.