2
$\begingroup$

I have been thinking about the Least Common Multiple and how it compares to $n!$

For $n=\{1,2,3,4,5,6\}$, the lcm for $n!$ is greater than $\sqrt{n!}$.

Is this always the case?

I would be interested in understanding how to analyze this.

Here's the thinking about this that I've done to this point:

Let $v(p,n)$ be the highest power of $p$ that is less or equal to $n$.

The least common multiple for $n!$ is:

$$\prod\limits_{p \le n}p^{v(p,n)}$$

I find it is much easier to reason about $\frac{(x+n)!}{x!}$ where I find in all cases:

$$\frac{(x+n)!}{x!\prod\limits_{p \le n}p^{v(p,x+n)}} \le (n-1)!$$

But applying this to the case of $n!$ is not interesting:

$$\frac{n!}{\prod\limits_{p \le n}p^{v(p,n)}} \le (n-1)!$$

  • the lcm of $n!$ increases each time a higher power or a prime is encountered.
  • Primes get rarer as $n$ increases.
  • Larger powers of primes also get rarer as $n$ increases.

What method would be used to compare the lcm of $n!$ with $\sqrt{n!}$? Under what conditions would the lcm of $n!$ be less than $\sqrt{n!}$?

$\endgroup$
4
$\begingroup$

Let $L_n=\text{lcm}(1,2,\ldots,n)$. Then $\ln L_n=\psi(n)$ where $$\psi(n)=\sum_{p\le n}\left\lfloor\frac{\ln n}{\ln p}\right\rfloor\ln p.$$ It is well-known that the Prime Number Theorem implies $\psi(n)\sim n$. By Stirling $\log\sqrt{n!}$ grows faster. Eventually $L_n<\sqrt{n!}$ for all large $n$.

$\endgroup$
  • 1
    $\begingroup$ Rosser and Schoenfeld (1962) Theorem 12, for $x > 0$ we have $\psi(x) < 1.03883 x.$ The maximum of $\psi(x) /x$ is achieved at $x = 113.$ $\endgroup$ – Will Jagy May 6 '17 at 19:58

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.