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

Question

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.

Answer 1

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}$.

Answer 2

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 ^_^.