Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

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

6 Answers 6

up vote 3 down vote accepted

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

share|improve this answer
    
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 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.

share|improve this answer

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$

share|improve this answer

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

share|improve this answer
5  
In fact, that is true for $N \ge 1$ –  Ross Millikan Feb 1 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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.