6
$\begingroup$

I want to find $\mathrm{lcm}(1, 2, 3, \ldots, n)$ where $2 \le n \le 10^8$ .

I'm trying to find a formula .

Please Help .

$\endgroup$
9
$\begingroup$

I claim that

$${\rm lcm}(1,2,3,\cdots,n)=\prod_p p^{\large\lfloor\log_p n\rfloor}.$$

Let's review what an LCM is: we say $\ell$ is an LCM of the elements of a finite set $S$ precisely if it has the following "universal property" (the GCD similarly has such a definition):

$$s\mid m~{\rm for~all~}s\in S ~~\iff~ \ell\mid m.$$

Which is to say that if we create a partial order on the set of things which are simultaneously multiples of everything in $S$, then $\ell$ is minimal in this collection. Now, call the product I defined earlier $\Pi$. Suppose $s\mid m$ for each $1\le s\le n$ and some integer $m$. Then in particular, for each prime number $p$, the highest power of $p$ that is $\le n$ (which is $p^{\lfloor\log_pn\rfloor}$ - check) will divide $m$, and hence (since all these things are coprime), their product, which is $\Pi$, will divide $m$. Thus

$$s\mid m{\rm ~for~all~}s\in S\implies \Pi\mid m.$$

Now we only need the reverse direction to show that $\Pi$ is an LCM. Thus, suppose $\Pi\mid m$ and let $1\le s\le n$. Then $s=\prod_p p^{e_p}$ has a unique prime factorization, and $e_p\le \lfloor\log_pn\rfloor$, so that in fact $p^{e_p}\mid p^{\lfloor\log_pn\rfloor}$ for each $p$, and hence $s\mid\Pi\mid m\implies s\mid m$. This finishes the proof.

Another possible formula is the exponential of the summatory Mangoldt function,

$${\rm lcm}(1,2,3,\cdots,n)=\exp\psi(n).$$

The reason this might be interesting is because of the connection between $\psi$ and the PNT.

$\endgroup$
4
$\begingroup$

This is OEIS A03418 where the formula $$a(n)=\prod p^{\lfloor(\log n/\log p\rfloor}$$ where p runs through primes not exceeding n is given, also

Recursive formula useful for computations: $a(0)=1; a(1)=1; a(n)=\operatorname{lcm}(n,a(n-1))$

$\endgroup$

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.