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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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
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|cite|improve this answer

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

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

The answer is

$$f(n)=lcm(1,2,3,...,n)=\prod\limits_{k=1}^{m-1}p_{k}^\left \lfloor \log_{p_{k}}(n) \right \rfloor$$

where $p_m$ is the first prime with $p_{m} > n$

This is actually related to one of the Chebyshev functions $\psi(x)$ being

$$f(n)=e^{\psi(x)}$$

There is a well-known formula that gives explicitly $\psi(x)$ (with a small technical and not very important difference relating the values on the jumps).

$$\psi_{0}(x)=x-\sum_\rho\frac{x^\rho}{\rho} - \log(2\pi) -\log(1-x^{-2})/2$$

where the summation goes over all zeros of Riemann zeta function

So a simple question going very deep immediately: 1 million dollars deep. Strange that we still know so little.

share|cite|improve this answer

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

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