# LCM of First N Natural Numbers

Is there an efficient way to calculate the least common multiple of the first n natural numbers? For example, suppose n = 3. Then the lcm of 1, 2, and 3 is 6. Is there an efficient way to do this for arbitrary n that is more efficient than the naive approach?

-
I thought you meant LCM, cause otherwise it is that simple as it is answered by Brandon below:) –  quapka Feb 1 '14 at 19:11
I did, sorry. Mistyped the question. –  Haxelgem Feb 1 '14 at 21:35

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...

-
I'd imagine this is the most efficient and easy to find algorithm. With the help of a prime sieve, such as Atkin, this algorithm could run in linear time for arbitrary large $n$ as long as you have the space to hold the sieve. But more than that, determining that a number is a prime power only requires log-linear time: mathoverflow.net/questions/106313/… –  Bryan Feb 1 '14 at 19:59

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.

-

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$

-

I think that as long as $N\geq 3$ (excluding 1) you will have that the gcd is 1, because your set will contain 2 and 3

-
In fact, that is true for $N \ge 1$ –  Ross Millikan Feb 1 '14 at 19:10

If I understand you right, and you want the GCD of {1, 2, 3, ..., n}, it's 1 for any n. The GCD of 1 and any number is always 1, owing to the fact that 1 only has one denominator (1). For any set, the GCD is always less than or equal to the smallest number in the set.

-

Let $p_k$ be the $k$-th prime. Let $n$ be the largest natural number such that $p_k\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}.$$

-