5
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ This seems to be tied to the distribution of primes, which means that a nice, self-contained, concrete answer will be difficult, to say the least. $\endgroup$ – Arthur Oct 11 '15 at 12:05
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Sounds like a good enough answer to show that the bound is finite. $\endgroup$ – Element118 Oct 13 '15 at 14:06
  • $\begingroup$ Finite and quite small, I'd say. $\endgroup$ – Ivan Neretin Oct 13 '15 at 14:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.