What is $$ \limsup_{n \to \infty} \frac{\log(\mathrm{lcm}(1,2, \dots, n))}{n} \ \ ?$$
$\begingroup$
$\endgroup$
3
-
2$\begingroup$ Limit exists and equals to $n$, it is equivalent form of Prime Numbers Theorem. $\endgroup$– Fedor PetrovCommented Sep 9, 2015 at 15:03
-
1$\begingroup$ @FedorPetrov you probably meant $1$ instead of $n$. $\endgroup$– PabloCommented Sep 9, 2015 at 15:23
-
1$\begingroup$ Ah, of course! Sorry. $\endgroup$– Fedor PetrovCommented Sep 9, 2015 at 15:29
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
4
It is well-known that $\operatorname{lcm}(1,\ldots,n) = e^{\psi(n)}$, where $\psi$ is the Chebyshev's function. Since $\psi(x) = x + o(x)$, as $x \to +\infty$, (a form of the Prime Number Theorem) it follows that actually $\lim_{n \to +\infty} \frac{\log(\operatorname{lcm}(1,\ldots,n))}{n} = 1$. (See Part 1 of G. Tenenbaum - Introduction to Analytic and Probabilistic Number Theory).
Not really a MO question, in my opinion.
-
$\begingroup$ The fact that the question was formulated in this specific way suggests it's some sort of exercise/homework. $\endgroup$– WojowuCommented Sep 9, 2015 at 15:19
-
$\begingroup$ @Wojowu it is not. I have just guessed the asymptotics after some wolfram calculations. That's all. $\endgroup$– PabloCommented Sep 9, 2015 at 15:24
-
2$\begingroup$ @Pablo Certainly I believe you, but it almost always helps to read in the question what sort of work OP did on the problem before asking at MO. $\endgroup$ Commented Sep 9, 2015 at 16:45
-
$\begingroup$ I'm glad to have this here ! I've got an algorithm whose complexity is exactly this log(gcd(1,...,n)). It is more or less theoretical, since I dont know any machine able to run it for n larger than 64. Anyway, II expected it to have a much bigger complexity than linear. I was surprised to see it working fast after implementing it. That's cool ! $\endgroup$– hivertCommented Nov 10, 2017 at 18:05
$\begingroup$
$\endgroup$
1
Well, certainly $L=\text{lcm}(1,...,n)$ is divisible by $p^k\leq n$. We can take $k$ up to $[\log_p n]\geq \frac{\log n}{\log p}-1$. So $$\log L\geq \sum_{p\leq n}\left(\frac{\log n}{\log p}-1\right)\log p\approx n$$ by the Prime Number Theorem. So the lim sup should be 1.
-
$\begingroup$ I don't think this argument is correct. The sum here equals $\sum_{p \le n} (\log n - \log p)$, but both $\sum_{p \le n} \log n$ and $\sum_{p \le n} \log p$ are asymptotic to $n$, by the prime number theorem. $\endgroup$ Commented Aug 5 at 0:45