LCM of First N Natural Numbers

Solution 1:

I don't know if you would call this efficient, but one simple way to calculate it is the following:

Let $f(n)=\text{LCM} \{1,2,3.., n \}$. Then

$$f(n+1)=\left\{ \begin{array}{l c} f(n) \cdot p & \mbox{if $\ n+1=p^k$} \\ f(n) & \mbox{otherwise} \\ \end{array} \right.$$

This is a simple recursive formula, which tells you that all you have to do is check if the integer is a power of primes. The closed forms from many answers are actually better answers, the problem is that for large $n$ you'd need to have the lists of all primes up to $n$, while this formula tests the integers one at a time (but you hit the factorization problem).

If $n$ is small the closed form is by far the fastest, and for large $n$ both ways are extremely long. This recursive approach might be a little faster when $n$ is big but not too big...

Solution 2:

Let $p_k$ be the $k$-th prime. Let $n$ be the largest natural number such that $p_n\le N$. Then the LCM of the first $N$ natural numbers is given by $$\prod_{k=1}^n p_k^{\,\lfloor \ln N / \ln p_k\rfloor}.$$

Solution 3:

After just a quick thought I think it might look something like this:

For $n \in \mathbb{N}$ $$ LCM(1,2,\ldots, n) = p_1^\frac{k_1}{p_1} \cdot p_2^\frac{k_2}{p_2} \cdots p_i^\frac{k_i}{p_i}, $$

where $p_i$ are prime numbers smaller or equal than $n$. And $k_i$ is the biggest integer smaller or equal than $n$ that is divisible by $p_i$.

But I might be wrong.

Solution 4:

Yes, I was going to say people were getting confused between your usage of greatest common $D$ivisor vs $D$enominator. You can check out sequence A003418 at the Online Encyclopedia of Integer Sequences. They provide several formulas, none of which are explicit though. They also have a list of them for $N\le 500$