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.

What's the smallest integer which is divisible by all integers $1, 2, \dots, n$? Is there a simple way to represent the answer? Call it $f(n)$ here.

Clearly factorial ($n!$) satisfies the condition of divisibility. But once you get to $f(4)$ (which is $12$), factorial ($24$) is too large, because it includes as factors both $4$ and $2$, which are redundant.

Multiplying all the prime numbers up to $n$ gives you another estimate, which is this time too low, because you need to include primes multiple times when they're repeated in the factorization of the inputs.

So the answer is somewhere between factorial, and the product of primes. Is there a simple answer?

share|improve this question
1  
It's the least common multiple of $\{1,\dots,n\}$, that is, $\mathrm{lcm}(1,2,\dots,n)$ –  Bill Cook Nov 8 '11 at 0:03
2  
Let $p_1,\dots,p_\ell$ be the primes less than or equal to $n$ and $k_i$ be the largest integer such that $p_i^{k_i}<n$, then $\mathrm{lcm}(1,2,\dots,n)=p_1^{k_1}\cdots p_\ell^{k_\ell}$ –  Bill Cook Nov 8 '11 at 0:06

4 Answers 4

up vote 5 down vote accepted

Given $n$, and given a prime number $p$, there's a non-negative integer $r=r(p)$ such that $p^r\le n\lt p^{r+1}$. The number you are looking for is the product of all the numbers $p^r$ over all the primes $p$.

It is known to be asymptotic to $e^n$, but this is not so easy to prove.

share|improve this answer

For more, see http://oeis.org/A003418 and references given there.

share|improve this answer

I guess I'll make my comments an answer...

It's the least common multiple of $\{1,\dots,n\}$, that is, $\mathrm{lcm}(1,2,\dots,n)$

Let $p_1,\dots,p_\ell$ be the primes less than or equal to $n$ and $k_i$ be the largest integer such that $p_i^{k_i}<n$, then $\mathrm{lcm}(1,2,\dots,n)=p_1^{k_1}\cdots p_\ell^{k_\ell}$.

share|improve this answer

Yes: $\text{lcm}(1,2,\ldots,n)$.

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.