Find the smallest positive integer which has all integers from 1 to n as factors

Question

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 code-golf 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

Answer 1

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!

Answer 2

05AB1E, 3 bytes

L.¿

Try it online!

Explanation

L     # range [1 ... input]
 .¿   # least common multiple

Answer 3

julia, 11 bytes

n->lcm(1:n)

Answer 4

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.

Answer 5

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

Answer 6

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

Answer 7

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

Answer 8

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.

Answer 9

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 vote — Byte count isn't everything — Support clever golfing!

Explanation

Ræl/
R    All numbers from 1 to the input
   / Reduce by
 æl  lowest common multiple

Answer 10

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.

Answer 11

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 ]

Answer 12

Octave, 25 bytes

@(n)lcm(num2cell(1:n){:})

Answer 13

Maxima, 29 bytes

f(n):=lcm(makelist(x,x,1,n));

Answer 14

Ruby, 22 bytes

->n{(1..n).reduce:lcm}

Answer 15

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)