Least Common Multiplier of First N Numbers

There is a famous result that is quite surprising if you see it the first time: The log of the least common multiplier of the first n integers is approximately n. The quotient converges to 1. Or to say it another way: It’s n-th root converges to e. You will find this result in the net. It is equivalent to the theorem about the distribution of prime numbers.

Let us check that with software.

>&lcm(makelist(n,n,1,500)), &log(float(%))/500

Of course, this infinite integer arithmetic of Maxima is not an effective way to check the result. Instead, we can use the following code to get the quotient for much higher numbers.

>longest sum(f*log(p))/N

This is based on the following observation. To compute the least common multiplier of 1  to n, we have to compute

\(p_1^{k_1} \cdot \ldots \cdot p_m^{k_m}\)

for all primes p(i) less then n, where k(i) is the largest number so that

\(p_i^{k_i} \le n\)

The logarithm of this product is exactly what is computed in the code above. If we make this a function and compute it for N from 10 to 5000, we get the following graph.


30. Juni 2017 von mga010
Kategorien: Uncategorized | Schreibe einen Kommentar

Schreibe einen Kommentar

Pflichtfelder sind mit * markiert