14
$\begingroup$

I computed the LCM for all natural numbers from 1 up to a limit $n$ and plotted the result over $n$. Due to the fast-raising numbers, I plotted the logarithm of the result and was surprised to find a (more or less) identity curve ($x=y$).

In other words, $LCM(1, 2, 3, ..., n)$ appears to be roughly the value $e^n$.

Is a there a simple explanation on why this is so?

$LCM(a, b, c, …)$ shall be defined as the least common multiple of all arguments $a, b, c, …$

plot of $ln(LCM(1, 2, 3, …, n))$ over $n$

$\endgroup$
3
  • 5
    $\begingroup$ Your observation is closely related to a theorem about the asymptotic behaviour of the Second Chebyshev Function $\psi(x)$, the logarithm of the lcm of the numbers $1$ to $x$. It turns out that $\lim_{x\to\infty}\frac{\psi(x)}{x}=1$. $\endgroup$ – André Nicolas Jan 20 '15 at 0:32
  • 2
    $\begingroup$ Why was @Xiang Yu's comment below not even noticed, even less addressed? $\endgroup$ – Did Sep 3 '17 at 12:12
  • $\begingroup$ Related: math.stackexchange.com/questions/834220/… $\endgroup$ – Watson Jun 8 '18 at 16:11
13
$\begingroup$

I think this is basically a different way to state exactly what André Nicolas said in a comment, but observe that the largest power of a given prime $p$ found as a factor in a number less than $n$ is explicitly given by $$ \lfloor\log_p(n)\rfloor=\left\lfloor\frac{\ln n}{\ln p}\right\rfloor $$ so we can write $LCM(n)=LCM(1,2,...,n)$ explicitly as $$ LCM(n)=\prod_{p\leq n}p^{\left\lfloor\frac{\ln n}{\ln p}\right\rfloor} $$ Applying $\ln(x)$ to both sides, we obtain $$ \begin{align} \ln(LCM(n))&=\sum_{p\leq n}\left\lfloor\frac{\ln n}{\ln p}\right\rfloor\cdot\ln p\\ &\approx \sum_{p\leq n}\frac{\ln n}{\ln p}\cdot\ln p\\ &=\ln n\cdot\sum_{p\leq n}1\\ &=\ln n\cdot \pi(n) \end{align} $$ where $\pi(n)$ denotes the function counting primes less than or equal to $n$. Now since by the prime number theorem we have $\pi(n)\sim\frac{n}{\ln n}$ so that these converge asymptotically, we get closer and closer to equality in the following approximation for $\ln(LCM(n))$: $$ \begin{align} \ln(LCM(n))&\approx\ln n\cdot\pi(n)\\ &\approx\ln n\cdot\frac{n}{\ln n}\\ &=n \end{align} $$ Applying the inverse of $\ln(x)$, namely $\text{e}^x$, then shows your statement. Note that the rounding off done by the floor functions becomes asymptotically insignificant.

$\endgroup$
3
  • $\begingroup$ Not as simple as I hoped for, but I managed. And furthermore I think it won't get much simpler than that. $\endgroup$ – Alfe Jan 20 '15 at 1:03
  • 6
    $\begingroup$ We need to consider the error term. Note that \begin{align} \log(\mathrm{lcm}\{1,\dots,n\})&=\sum_{p\leq n}\left\lfloor \frac{\log n}{\log p}\right\rfloor \log p=\sum_{p\leq n} (\frac{\log n}{\log p}+O(1))\log p\\ &=\sum_{p\leq n}\log n+O(\log p)=\pi(n)\log n+O(\sum_{p\leq n}\log n)\\ &=\pi(n)\log n+O(\theta (n)), \end{align} where $\theta$ is the first Chebyshev function. Since $\theta(x)\sim x$, the error term is the same size as the main term! $\endgroup$ – Xiang Yu Apr 13 '16 at 14:33
  • 3
    $\begingroup$ "Note that the rounding off done by the floor functions becomes asymptotically insignificant." A missing part, if true. $\endgroup$ – Did Sep 3 '17 at 12:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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