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