Picking random integers $a_i$ until the $\gcd(a_1,a_2,\dots,a_n)$ is 1

Question

When we say "pick a random integer", the integers are in the range $[1, N]$.

Problem:

Consider the following instructions:

Pick a random integer.

Find the greatest common divisor of all the integers which have been picked so far.

If the greatest common divisor is not 1, go back to the first step to pick a random integer.

When this process ends, let $X$ be the total number of integers you have picked. I would like to find $E(X)$ in terms of $N$.

Example of this process: (where $N=4$)

1. I picked the random integer, 2.
2. $\gcd(2)=2$
3. I picked another random integer, 4.
4. $\gcd(2, 4) = 2$
5. I picked another random integer, 2.
6. $\gcd(2, 4, 2) = 2$
7. I picked another random integer, 3.
8. $\gcd(2, 4, 2, 3) = 1$

In total, I picked $X=4$ integers, $2, 4, 2, 3$.

My ideas:

A easy upper bound can be shown to be $N$, which is the expected number of numbers to be chosen before getting a 1.

Let $M(g, N)$ be the expected number of integers I will need after getting $g$ as the greatest common divisor of the integers so far.

We have $E(X)=1+\frac{\sum_{i=1}^NM(g, N)}{N}$.

Small cases:

$N=1\rightarrow E(X)=1$

$N=2\rightarrow E(X)=2$

Answer 1

(not an answer, but still probably worth a look)

I'll get you a better upper bound.

What is the probability that our gcd is divisible by two? It is $1\over2$ after the first step, $1\over4$ after the second, and so on. The probability of being divisible by 3, likewise, behaves as ${1\over3^n}$; then goes 5 and the rest of primes. What is the probability of gcd being divisible by anything at all except 1? Obviously, no more than the sum of the above (actually, less than that, because they overlap): ${1\over4}+{1\over9}+{1\over25}...$ after step 2, $\sum\limits_{i=1}^\infty{1\over p_i^3}$ after step 3, and so on. Thus the expected number of steps would be bounded from above with $1+1+\sum\limits_{i=1}^\infty{1\over p_i^2}+\sum\limits_{i=1}^\infty{1\over p_i^3}+\dots = 2+\sum\limits_{i=1}^\infty{1\over p_i(p_i-1)} < 2+\sum\limits_{i=2}^\infty{1\over i(i-1)}=3$.

Note that the obtained bound is independent of $N$.