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

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

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. — xnor, Jan 4, 2017 at 11:02

Community · Accepted Answer · 2017-04-13 12:39:03Z

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!

I might be being stupid, but can't you use | in place of or. — busukxuan, Jan 4, 2017 at 11:59
@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. — xnor, Jan 4, 2017 at 12:06
@xnor Oh I see, or on integers is an arithmetic operation huh... — busukxuan, Jan 4, 2017 at 12:08
I don't think it's a question that you have a golfing problem ;) — Kade, Jan 4, 2017 at 12:57
@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. — xnor, Jan 4, 2017 at 20:15

Emigna · Accepted Answer · 2017-01-04 11:05:58Z

10

05AB1E, 3 bytes

L.¿

Try it online!

Explanation

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

answered Jan 4, 2017 at 11:05

Emigna

53k5 gold badges42 silver badges162 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

8

julia, 11 bytes

n->lcm(1:n)

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Jan 4, 2017 at 12:00

rahnema1

5,6651 gold badge14 silver badges22 bronze badges

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, 2017 at 12:01
\$\begingroup\$ I am also relatively new to julia:) \$\endgroup\$
– rahnema1
Jan 4, 2017 at 12:06

Add a comment |

Addison Crump · Accepted Answer · 2017-01-04 16:34:55Z

6

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.

edited Jan 4, 2017 at 16:34

answered Jan 4, 2017 at 12:26

Addison Crump

11.2k1 gold badge43 silver badges89 bronze badges

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, 2017 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, 2017 at 15:02
\$\begingroup\$ @MartinEnder So my answer is LCM@@Range@#&? How do I call that? \$\endgroup\$
– Addison Crump
Jan 4, 2017 at 16:16
1

\$\begingroup\$ ...&[5] or assign it to a variable f=... and then f[5]. \$\endgroup\$
– Martin Ender
Jan 4, 2017 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, 2017 at 16:27

| Show 2 more comments

Arnauld · Accepted Answer · 2017-01-04 12:57:32Z

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

edited Jan 4, 2017 at 12:57

answered Jan 4, 2017 at 12:00

Arnauld

192k20 gold badges175 silver badges636 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

5

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

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Jan 4, 2017 at 12:19

Titus

14.7k1 gold badge23 silver badges41 bronze badges

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, 2017 at 16:56
\$\begingroup\$ @user59178 PHP now beats JavaScript. Thanks for the push! \$\endgroup\$
– Titus
Jan 4, 2017 at 17:46

Add a comment |

Brad Gilbert b2gills · Accepted Answer · 2017-01-04 15:02:30Z

3

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

answered Jan 4, 2017 at 15:02

Brad Gilbert b2gills

13.2k1 gold badge18 silver badges33 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

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.

score 2 · Accepted Answer · 2017-01-04 11:23:18Z

2

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

edited Jan 4, 2017 at 11:23

answered Jan 4, 2017 at 11:07

user62131

8

\$\begingroup\$ I chuckled a bit, because in Norweigan "Ræl" means "junk" or "shit". \$\endgroup\$
– Alec
Jan 4, 2017 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 - reinstate Monica
Jan 4, 2017 at 14:48

Add a comment |

Christian Sievers · Accepted Answer · 2017-01-04 12:08:06Z

2

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 ]

answered Jan 4, 2017 at 12:08

Christian Sievers

7,1301 gold badge18 silver badges25 bronze badges

Add a comment |

busukxuan · Accepted Answer · 2017-01-04 17:13:57Z

2

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.

edited Jan 4, 2017 at 17:13

answered Jan 4, 2017 at 11:43

busukxuan

2,8089 silver badges23 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

1

Octave, 25 bytes

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

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Jan 4, 2017 at 11:58

rahnema1

5,6651 gold badge14 silver badges22 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

0

Maxima, 29 bytes

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

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Jan 4, 2017 at 12:04

rahnema1

5,6651 gold badge14 silver badges22 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

0

Ruby, 22 bytes

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

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Jan 4, 2017 at 12:05

G B

21.9k1 gold badge20 silver badges53 bronze badges

Add a comment |

idrougge · Accepted Answer · 2017-01-04 14:56:21Z

0

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)

answered Jan 4, 2017 at 14:56

idrougge

6714 silver badges6 bronze badges

Add a comment |

Stack Exchange Network

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

Test cases

15 Answers 15

Python, 46 bytes

05AB1E, 3 bytes

julia, 11 bytes

Wolfram Language, 20 13 bytes

JavaScript (ES6), 54 50 bytes

Test cases

PHP, 61 52 48 bytes

Perl 6, 13 bytes

Expanded:

Perl, 32 bytes

Jelly, 4 bytes

Explanation

GAP, 14 bytes

Sage, 33 28 bytes

Octave, 25 bytes

Maxima, 29 bytes

Ruby, 22 bytes

REXX, 61 bytes

Linked

Hot Network Questions

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

Test cases

15 Answers 15

Python, 46 bytes

05AB1E, 3 bytes

julia, 11 bytes

Wolfram Language, 20 13 bytes

JavaScript (ES6), 54 50 bytes

Test cases

PHP, 61 52 48 bytes

Perl 6, 13 bytes

Expanded:

Perl, 32 bytes

Jelly, 4 bytes

Explanation

GAP, 14 bytes

Sage, 33 28 bytes

Octave, 25 bytes

Maxima, 29 bytes

Ruby, 22 bytes

REXX, 61 bytes

Linked

Related

Hot Network Questions