6
$\begingroup$

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?

  • 1
    It's the least common multiple of $\{1,\dots,n\}$, that is, $\mathrm{lcm}(1,2,\dots,n)$2011-11-08
  • 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}$\mathrm{lcm}(1,2,\dots,n)=p_1^{k_1}\cdots p_\ell^{k_\ell}$2011-11-08
  • 0
    As for asymptotic behaviour of $\text{lcm}(1,\dots,n)$ see http://math.stackexchange.com/questions/8342202016-09-16

5 Answers 5

5

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.

4

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

3

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}

1

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.

0

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