Two $n$-bit numbers (i.e. $2^{n-1} \le x_i \le 2^n - 1$) are chosen uniformly randomly. What is their least common multiple?
I know the minimum is $x_1=x_2$ when they collide and the maximum is $x_1*x_2$ when they are coprime. However, I would like to know:
- The expected value.
- The minimum when $x_1 \neq x_2$.
- The bounds in terms of $n$ (when distinct).
If there is no answer in general, the approximation for $n \to \infty$ would be great.
The exact expected value will probably be very hard to compute because it depends in part on how many primes there are between $2^{n-1}$ and $2^n - 1$, and the values of those primes. It may be possible to get asymptotics, e.g. if $f(n)$ is the expected value you may be able to find a function $g(n)$ such that $\lim_{n \to \infty} f(n)/g(n) = 1$. I don't see how to do that off the top of my head though
The minimum possible value you can get for $x_1 \neq x_2$ is when $x_1 = 2^{n-1}$ and $x_2 = 3*2^{n-2}$, and in this case the LCM is $3*2^{n-1}$.