LCM of $n$ consecutive natural numbers

Question

Is there an efficient way to calculate the least common multiple of $n$ consecutive natural numbers? For example, suppose $a = 3$ and $b = 5$, and you need to find the LCM of $(3,4,5)$. Then the LCM of $3,4$ and $5$ is $60$. Is there an efficient way to do this for arbitrary $a$ and $b (a\leq b)$ that is more efficient than the naive approach$?$

Edit: What if I know the LCM of (1,2,3,4,..a) and the LCM of (1,2,3,..b). Is it possible to get the LCM of (a,a+1,..b) ?

Answer 1

A very interesting trick to find $LCM$,though its not exactly the same as your question.It does not deal with consecutive set of numbers.-

Let the numbers are-$(8,12).$

Steps:-

1.Find their $GCD$-Here it is $4.$

2.Now divide any of the given numbers by the $GCD$.Let us divide $8$ by $4$ here.It is equal to $2$.

3.Now,multiply it by the other number.Here it is $2*12=24$.It's your LCM.

Answer 2

To find the $\text{lcm}$ of the first $n$ natural numbers, we can use the relation $n-1=\sum_{k=2}^{n}{e^{2i\pi Q}}$ and solve for $Q$ using numerical methods. This ends up getting quite tricky. We need to find the zeroes of the function $U(Q)=\sqrt{\left(\sum_{k=2}^n{\cos{\frac{2\pi Q}{k}}}\right)^2+\left(\sum_{k=2}^n{\sin{\frac{2\pi Q}{k}}}\right)^2}+1-n$. Finding the first root after $Q=0$ is quite difficult because the function is non-differential at many points. In fact, interpolation is no use either because the function oscillates at a rate approximately proportional to simply searching over $\mathbb Z$. That said, we can still find the $\text{lcm}$ for small enough $n$ by searching the utility space linearly over $\mathbb Z$.

For example, to find the $\text{lcm}$ of $\{1,2,3, . . . 10\}$, we compute $U(Q)_{|n=10}$ starting at $Q=1$ and continue until $U(Q)_{|n=10}$ is close enough to $0$. Taking roughly $15$ms on my machine, the number $1154160$ is produced. This is one answer to your question on a way to compute the LCM using a root finding algorithm. However, while thinking of ways to restrict the search space of the algorithm, I discovered a closed form solution to the problem, which I will post as a separate answer.

Answer 3

$$\text{lcm}{\left\{1,2,3,...,N\right\}}=\prod_{p\in\text{prime}}{p^{\lfloor\log_pn\rfloor}}$$

For example, $\text{lcm}\{1,2,3,...,40\}=5342931457063200$