# Approximate LCM (Least Common Multiple) of $n$ random $k$-digit numbers

I choose $$n$$ different $$k$$-digit numbers randomly. I was wondering, roughly, what one can expect their LCM (least common multiple) to be? Preferably in Big O (or Big $$\Theta$$) notation. I'm particular interested in the dependence on $$k$$ and $$n$$. Feel free to assume $$n \ll e^{O(k)}$$, or any other reasonable assumptions.

As related examples, $$LCM(1,\ldots,n) \in O(e^n)$$, and a randomly chosen $$k$$-digit number has a probability $$O\left(\frac{1}{k}\right)$$ of being prime.

For bonus points, I'd also love an answer for the same question, but for the GCD (greatest common divisor), instead of the LCM.

• I suspect that the GCD very quickly becomes 1 for all but the smallest $n$ (if I recall correctly, the probability of gcd being 1 for $n = 2$ is, asymptotically for large $k$, equal to $6/\pi^2$, but I don't know how large the gcd is expected to be when it isn't 1, or exactly how it works for larger $n$). Of course, one could ask about how fast it is expected to go to 1 as a function of $n$. Apr 27, 2022 at 7:16
• @Arthur Yeah, I'm sure the GCD will ultimately approach 1, but I'm mostly interested in the average, as well as the asymptotic dependence on $k$ and $n$ as to how rapidly the limit is approached. Apr 27, 2022 at 7:35

An upper bound for the gcd is easy. Assume n ≥ 2 integers with linear distribution in the range 1 .. M. The chance that a number is divisible by k is ≤ 1/k. (For example k = 5, M = 113, the probability is 22 / 113 < 1/5).

The gcd of n numbers is k if they are all divisible by k and have no larger common factor; the probability for this is at most (1/k)^n. The expected value of the gcd is the sum of k * probability (gcd = k), so at most the sum of (1 / k)^(n-1) for k = 1 to M.

You should be able to find a lower bound as well, and you'll find that for n = 2 the expected value will be ln M + o(1), for n = 3 close to pi^2 / 6, and for larger n the sum converges very quickly and the expected value of the gcd is not much above 1 + 2^(1-n).

For fixed n, M you can calculate the expected value of the gcd exactly (except for rounding errors) in O (M log M):

Your integers are in the range 1 ≤ x ≤ M. Of these M values, exactly $$\lfloor M/k \rfloor$$ are divisible by k. There are exactly $${\lfloor M/k \rfloor}^n$$ tuples of n numbers with the common divisor k. For these tuples, the gcd is k, unless the gcd is a multiple of k. So for M/2 < k ≤ M, the number of tuples with gcd = k is 1. Then you calculate the number of tuples for k in descending order down to k = 1: The number is $${\lfloor M/k \rfloor}^n$$, minus the number of tuples with gcd = 2k, 3k, 4k, for all multiples of k ≤ M. You get the probability that the gcd of a random tuple is k by dividing by $$M^n$$. You get the expected value of the gcd by calculating the sum of k multiplied by the gcd.

If n is large you would first figure out which gcd's are so unlikely that their contribution to the sum is less than the rounding error in your calculation. If say n ≥ 40 then the expected value of the gcd is practically $$1 + 2^{-n}$$ because $$3^{40} ≈ 1.2 \cdot 10^{19}$$.

I think I've got it for the LCM! Basically, the LCM of $$n$$ random $$k$$-digit numbers will have around $$n\cdot k$$ digits.

Here's a rough proof. We have

$$\mathbb{E}(\ln(LCM_{n,k})) \approx \sum_{p\in primes}^{e^k}\sum_{i=1}^{k/\ln(p)}\ln(p)\left(1-\left(1-\frac{1}{p^i}\right)^n\right)$$ To explain some of the parts of this:

• We look at the expectation of the log of the LCM so that the different factors split into a sum, allowing us to use linearity of expectation
• The outer sum is over all primes up to $$e^k$$. The inner sum is for the powers of those primes. E.g. having a factor of 3 will add on $$\ln(3)$$, also having a factor of 9 will further add on a factor of $$\ln(3)$$, etc. The largest power a factor of $$p$$ that can show up is $$\approx k/\ln(p)$$.
• The probability that a factor $$p^i$$ will be present in the LCM is 1 minus the probability that $$p^i$$ isn't present in each of the $$n$$ numbers.

Anyways, from there we make some manipulations and approximations

$$\mathbb{E}(\ln(LCM_{n,k})) \approx \sum_{p\in primes}^{e^k}\ln(p)\sum_{i=1}^{k/\ln(p)}\left(1-\left(1-\frac{1}{p^i}\right)^n\right)$$ $$\approx \sum_{p\in primes}^{e^k}\ln(p)\sum_{i=1}^{k/\ln(p)}\left(1-\left(1-\frac{n}{p^i}\right)\right)$$ $$\approx n\sum_{p\in primes}^{e^k}\ln(p)\sum_{i=1}^{k/\ln(p)}\frac{1}{p^i}$$ $$\approx n\sum_{p\in primes}^{e^k}\ln(p) \frac{\frac{1}{p}-\frac{1}{p^{k/\ln(p)+1}}}{1-\frac{1}{p}}$$ $$\approx n\sum_{p\in primes}^{e^k}\frac{\ln(p)}{p}$$ $$\approx O(n \cdot k)$$

Overall, a very, VERY elegant result ^_^. For the record, I took advantage of $$p$$ being very large for the most part, and $$n$$ being relatively small.

So ultimately, we get that the LCM will be roughly on the order of $$e^{n\cdot k}$$ (in the geometric average sense). Given that each of the numbers is already on the order of $$e^k$$, what this says is that, each time you add another number, the LCM goes up by $$k$$ digits, and the $$LCM$$ of $$n$$ numbers will have $$n$$ times as many digits.

Let me know if I'm wrong, or made any mistakes.

FWIW, I did a simple experiment, and the LCM of 3 random 100-digit numbers was indeed right around 300-digits, so I think I'm right ^_^.