22
\$\begingroup\$

The question's pretty much described by the title: write a program or function that takes a positive integer n as input, and returns the smallest positive output which has all integers from 1 to n as factors. (Another way of looking at this is that you're looking for the least common multiple of the integers from 1 to n.)

This is a challenge, so the shortest entry in bytes wins.

Inspired by this challenge. (This challenge is basically the inverse of that one.)

Test cases

  • Input: 1; Output: 1
  • Input: 6; Output: 60
  • Input: 19; Output: 232792560
  • Input: 22; Output: 232792560

You don't need to worry about integer precision issues (unless your language has integers so small that this would trivialise the problem). If your language does have bignums, though, you might also want to test your program on this case, just for fun:

  • Input: 128; Output: 13353756090997411579403749204440236542538872688049072000
\$\endgroup\$
  • \$\begingroup\$ Could you add some test cases? \$\endgroup\$ – Zgarb Jan 4 '17 at 10:57
  • 2
    \$\begingroup\$ I remember golfing this precise task and have code already written for it in a file created in August, but I can't find a dupe. \$\endgroup\$ – xnor Jan 4 '17 at 11:02
  • \$\begingroup\$ @Zgarb: I've added some cases as you requested. \$\endgroup\$ – user62131 Jan 4 '17 at 11:02
  • \$\begingroup\$ @xnor Related \$\endgroup\$ – Zgarb Jan 4 '17 at 11:03
  • \$\begingroup\$ I take it the input is positive? \$\endgroup\$ – xnor Jan 4 '17 at 11:05

15 Answers 15

27
\$\begingroup\$

Python, 46 bytes

g=lambda n,c=0:n<1or(c%n<1)*c or g(n,c+g(n-1))

Take that, past xnor!


50 bytes:

g=lambda n,i=1:n<1or(i*n%g(n-1)<1)*i*n or g(n,i+1)

I apparently golfed this problem 5 months ago, and I don't remember how this code works or why I golfed it. I think I have a golfing problem.

(Edit: It's from this answer. Thanks to Dennis for inspiring the solution and saving 4 bytes.)

Apparently, this code recursively finds lcm(1..n) as lcm(lcm(1..n-1),n). So, the function g expresses g(n) as the smallest positive multiple i*n of n that's also a multiple of g(n-1). (It could instead search multiples of g(n-1) for multiples of n, but this is golfier because g(n-1) only needs to be referenced once. Thanks to Dennis for this improvement.)

Here's the rest of the file, full of other golfing attempts:

f=lambda a,b:a and f(b%a,a)or b
g=lambda n:reduce(lambda a,b:a*b/f(a,b),range(1,n+1))

f=lambda a,b:a and f(b%a,a)or b
g=lambda n:n==1 or n*g(n-1)/f(n,g(n-1))

import math
g=lambda n:n==1 or n*g(n-1)/math.gcd(n,g(n-1))

g=lambda n,k=1:k*all(k%~i==0for i in range(n))or g(n,k+1)
g=lambda n,k=1:min(k%~i for i in range(n))and g(n,k+1)or k

l=lambda a,b:a%b and l(b,a%b)*a/(a%b)or a
g=lambda n:n<1or l(n,g(n-1))

g=lambda n,i=1:n==0 or (g(n-1)*i if g(n-1)*i%n==0 else g(n,i+1))

g=lambda n,i=1:n<1or g(n-1)*i*(g(n-1)*i%n<1)or g(n,i+1)

g=lambda n,i=1:n<1or(i*g(n-1)%n<1)*i*g(n-1)or g(n,i+1)

g=lambda n,r=1,c=1:r if n<2 else (g(n-1,r,r)if r%n==0 else g(n,r+c,c))

g=lambda n,r=1,c=1:r*(n<1)or r%n and g(n,r+c,c)or g(n-1,r,r)

g=lambda n,i=1:n<1or(i*g(n-1)%n or i)*g(n-1)or g(n,i+1)

def g(n):
 if n==0:return 1
 a=b=g(n-1)
 while b%n:b+=a
 return b

g=lambda n,i=1:n<1or g(n-1)*i%n and g(n,i+1)or g(n-1)*i

g=lambda n:n<1or min(range(n,3**n,n),key=g(n-1).__rmod__)

g=lambda n,i=1:n<1or(i*n%g(n-1)<1)*i*n or g(n,i+1)

r=n=input()
while n:
 c=r
 while r%n:r+=c
 n-=1
print r

r=n=input()
while n:
 c=r
 while r%n:r+=c
 n-=1
print r

r=1
for n in range(input()):
 c=r
 while r%~n:r+=c
print r

r=n=input()
while n:
 exec"r+=c*(r%n>0);"*n
 n-=1;c=r
print r

r=n=input();exec("r+=r%n and c;"*n+"n-=1;c=r;")*n;print r

It's eerie looking at my own past work. In trying to golf it, I keep thinking "maybe I can save some bytes by ..." and then seeing there's already a piece of code that attempted to do just that.

You think you've thought of everything, past xnor? Well, I'll show you!

\$\endgroup\$
  • \$\begingroup\$ I might be being stupid, but can't you use | in place of or. \$\endgroup\$ – busukxuan Jan 4 '17 at 11:59
  • 1
    \$\begingroup\$ @busukxuan No, or is different from | on integers, a or b equals a if a is nonzero, and otherwise b. I'm using it as a conditional to use the current c only if both nonzero and a multiple of n. \$\endgroup\$ – xnor Jan 4 '17 at 12:06
  • \$\begingroup\$ @xnor Oh I see, or on integers is an arithmetic operation huh... \$\endgroup\$ – busukxuan Jan 4 '17 at 12:08
  • 2
    \$\begingroup\$ I don't think it's a question that you have a golfing problem ;) \$\endgroup\$ – Kade Jan 4 '17 at 12:57
  • 2
    \$\begingroup\$ @Adnan Thanks, mystery solved! Funnily enough, searching the exact code didn't find it, whether on SE search, google, or code-searching engines that claim to preserve punctuation. Also unclear why my file was created two months after the post. \$\endgroup\$ – xnor Jan 4 '17 at 20:15
10
\$\begingroup\$

05AB1E, 3 bytes

L.¿

Try it online!

Explanation

L     # range [1 ... input]
 .¿   # least common multiple
\$\endgroup\$
8
\$\begingroup\$

julia, 11 bytes

n->lcm(1:n)
\$\endgroup\$
  • 1
    \$\begingroup\$ My first thought was literally "Julia could do it, though I am too lazy to find out enough to actually write a snippet" xP \$\endgroup\$ – busukxuan Jan 4 '17 at 12:01
  • \$\begingroup\$ I am also relatively new to julia:) \$\endgroup\$ – rahnema1 Jan 4 '17 at 12:06
6
\$\begingroup\$

Wolfram Language, 20 13 bytes

LCM@@Range@#&

Applies a range from 1 to x, then applies it to LCM. To run this, append [<input>].

7 bytes (!) shaved off by Martin.

\$\endgroup\$
  • 1
    \$\begingroup\$ It is worth noting that I almost never use this language, so this can almost certainly be golfed. \$\endgroup\$ – Addison Crump Jan 4 '17 at 12:26
  • 2
    \$\begingroup\$ you can use prefix notation to save two bytes: f@x_:=LCM@@Range@x or define an operator to save another: ±x_:=LCM@@Range@x, but it's usually shortest to use an unnamed function: LCM@@Range@#&. \$\endgroup\$ – Martin Ender Jan 4 '17 at 15:02
  • \$\begingroup\$ @MartinEnder So my answer is LCM@@Range@#&? How do I call that? \$\endgroup\$ – Addison Crump Jan 4 '17 at 16:16
  • 1
    \$\begingroup\$ ...&[5] or assign it to a variable f=... and then f[5]. \$\endgroup\$ – Martin Ender Jan 4 '17 at 16:23
  • \$\begingroup\$ A function using # as variable and ending in & is called a "Pure Function." Here's a good guide on how it works. I recommend changing your answer to LCM@@Range@#& as it is 8 bytes shorter than your version. \$\endgroup\$ – JungHwan Min Jan 4 '17 at 16:27
5
\$\begingroup\$

JavaScript (ES6), 54 50 bytes

f=(n,L=1,a=L,b=n)=>n?b?f(n,L,b,a%b):f(n-1,n*L/a):L

Test cases

f=(n,L=1,a=L,b=n)=>n?b?f(n,L,b,a%b):f(n-1,n*L/a):L

console.log( 1, f( 1));
console.log( 6, f( 6));
console.log(19, f(19));
console.log(22, f(22));

\$\endgroup\$
5
\$\begingroup\$

PHP, 61 52 48 bytes

saved 9 bytes thanks to @user59178, 4 bytes by merging the loops to one.

Recursion in PHP is bulky due to the function key word; so I use iteration.
And with a "small" trick, I now even beat JS.

while(++$k%++$i?$i>$argv[1]?0:$i=1:$k--);echo$k;

takes input from command line argument. Run with -r.

breakdown

while(++$k%++$i?    # loop $i up; if it does not divide $k
    $i>$argv[1]?0       # break when $i is larger than input
    :$i=1               # while not, reset $i and continue loop with incremented $k
    :$k--);         # undo increment while $i divides $k
echo$k;         # print $k

ungolfed

That´s actually two loops in one:

while($i<=$argv[1])     # break when $i (the lowest non-divisor of $k) is >input
    for($k++,           # loop $k up from 1
        $i=0;$k%++$i<1;);   # loop $i up from 1 while it divides $k
echo$k;                 # print $k
\$\endgroup\$
  • 1
    \$\begingroup\$ You can save 9 bytes by moving the $k++ into the setup for the inner loop: you don't have to initialise it or decrement it at the end & $n becomes completely unnecessary. Then at least PHP will be beating the REXX answer. \$\endgroup\$ – user59178 Jan 4 '17 at 16:56
  • \$\begingroup\$ @user59178 PHP now beats JavaScript. Thanks for the push! \$\endgroup\$ – Titus Jan 4 '17 at 17:46
3
\$\begingroup\$

Perl 6, 13 bytes

{[lcm] 1..$_}

Try it

Expanded:

{  # bare block lambda with implicit parameter 「$_」

  [lcm]      # reduce using 「&infix:<lcm>」

    1 .. $_  # a Range from 1 to the input ( inclusive )
}
\$\endgroup\$
2
\$\begingroup\$

Perl, 32 bytes

31 bytes of code + -p flag.

$.++while grep$.%$_,2..$_;$_=$.

Try it online!

The code test every number (starting from 1 and incrementing by 1 each time) to find a common multiple. So it's rather slow even for not so large numbers.

grep$.%$_,2..$_ returns an array of the elements of the range 2..$_ (where $_ is the input) that satisfy $.%$_!=0 ($. is the number we're trying), ie. an array of the elements that aren't a divisor of $.. While this array isn't empty, $.++ is incremented. At the end, $_ is set tp $. and implicitly print thanks to -p flag.

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

Jelly, 4 bytes

Ræl/

Try it online!

When I posted the question, I thought Jelly didn't have a built-in for this. We were discussing the problem in chat, though, and someone pointed out that it does, so I decided I might as well write the obvious solution using it. (That said, 4 bytes is quite a lot for a challenge that's mostly solved via a built-in! It may well be possible to beat this in some other language, or even in Jelly itself. Update: I see 05AB1E beat this while I was writing out the entry.)

Ideally, this answer shouldn't be voted on either way, in order to let answers which require more skill shine; it's not wrong, but it's also not all that interesting. As the community advert says:

Know how to voteByte count isn't everythingSupport clever golfing!

Explanation

Ræl/
R    All numbers from 1 to the input
   / Reduce by
 æl  lowest common multiple
\$\endgroup\$
  • 8
    \$\begingroup\$ I chuckled a bit, because in Norweigan "Ræl" means "junk" or "shit". \$\endgroup\$ – Alec Jan 4 '17 at 11:55
  • 1
    \$\begingroup\$ @Alec It would be a great reason to upvote this answer if the unpublished intent of the original challenge was to point out that when you accidentally create "real" words when you are coding, it can actually mean other shit. \$\endgroup\$ – Keeta Jan 4 '17 at 14:48
2
\$\begingroup\$

GAP, 14 bytes

n->Lcm([1..n])

Checking the test cases:

gap> List([1,6,19,22,128], n->Lcm([1..n]) ); 
[ 1, 60, 232792560, 232792560, 
  13353756090997411579403749204440236542538872688049072000 ]
\$\endgroup\$
2
\$\begingroup\$

Sage, 33 28 bytes

No golfing tricks here, but somehow I had an urge to post this xP

l=lambda n:lcm(range(2,n+1))

Too bad Sage's lcm only takes 2 arguments, unlike Octave's variadic one.
It can actually take a list as input.

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

Octave, 25 bytes

@(n)lcm(num2cell(1:n){:})
\$\endgroup\$
0
\$\begingroup\$

Maxima, 29 bytes

f(n):=lcm(makelist(x,x,1,n));
\$\endgroup\$
0
\$\begingroup\$

Ruby, 22 bytes

->n{(1..n).reduce:lcm}
\$\endgroup\$
0
\$\begingroup\$

REXX, 61 bytes

arg a
do m=1 until a<n
  do n=1 to a until m//n>0
  end
end
say m

(Indented for readability)

\$\endgroup\$