LCM of randomly selected integers

Question

What is the expected LCM of 21 randomly selected positive integers under 10000000?

How would someone even approach this problem?

EDIT: The positive integers are chosen with replacement.

Answer 1

Let $1 \leq a_1, \dots, a_n \leq N$ be number chosen uniformly at random. What is their least common multiple?

What is the highest power of $2$ dividing any of the $a_1, \dots, a_n$?

• All the numbers are odd with probability $(1 - \frac{1}{2})^n$
• All the numbers are odd or even (but not divisible by 4) with probability $(1 - \frac{1}{4})^n$
• All the numbers are odd or even (but not divisible by 8) with probability $(1 - \frac{1}{8})^n$
• ...

So the expected power of $2$ dividing all these numbers is (this number might simplify):

$$ \mathbb{E}_2 = \sum_{k \geq 0} \Big(2^k - 2^{k-1} \Big) \left[1- \left( 1- \tfrac{1}{2^k} \right)^n \right]$$

A similar story for $\mathbb{E}_3, \mathbb{E}_5, \mathbb{E}_7$ etc; multiply your answers

$$ \mathbb{E} = \prod_{p } \mathbb{E}_p$$

---

See also: Expectation of the maximum of i.i.d. geometric random variables a quick look confirms there is no closed-form answer.

In your case $n = 21$ and $N = 1,000,000$ so we can hope for an estimate.

---

One way to state the prime number theorem is that $\mathrm{lcm}(1,2,\dots, n) = e^n$ So the least common multiple is growing exponentially fast in $n$. In your case, there are $n = 21$ numbers ranging from $1$ to $N = 10^6$. Perhaps

$$ \mathbb{E} \approx e^{n} \times \left(\frac{N}{n}\right)^n \approx \frac{N^n}{n!} = \frac{10^{21}}{ 21!} \approx \frac{10^{21}}{ 5 \times 10^{19}} = 40 $$

Still doesn't seem quite right. See Granville Prime Number Races)

Answer 2

Whether you chose the integer with replacement or not is unlikely to make a difference: the probability to have 21 different integers in your set of 21 is $$\exp\left(\sum_{i=0}^{20}\log\left(1-\frac i{10^7}\right) \right)\simeq 1 - \frac{20⋅21}{2⋅10^7}=1-2.1⋅10^{-5}$$.

A paper by Cilleruelo, Rué, Šarka and Zumalacárregui (arXiv:1112.3013 , J. Num. Th. 144 92) specifically addresses similar questions. They compute $\DeclareMathOperator\lcm{lcm}$ $$ψ(A)=\log\lcm\{a:a∈A\} $$ for random subsets $A⊆\{1…n\}$ of size $|A|=k(n)$ when $n→∞$. When $k(n)→∞$, their theorem 1.2 says that, almost surely $$ψ(A)=k\frac{\log\frac nk}{1-\frac kn}\left(1+O\left(e^{-C\sqrt{\log k}}\right)\right), $$ for a constant $C$.

In your case, you have $n=10^7$, $k=21$. Since $k$ is not really large, you should look into the paper to see how this is proven, and to which extent it applies to your case. Boldly assuming $k=21→∞$ (I know !), would led to

$$ψ(A)=21\frac{19.16}{1-2.1⋅10^{-6}}\left(1+O\left(e^{-1.74C}\right)\right) ∼ 400 \text{, if $C$ is big enough.} $$

In other words, we would have $\lcm(A)∼e^{400}∼5⋅10^{173}$ if my rough unjustified approximations are correct.