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$
1
  • $\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, 2015 at 12:05

1 Answer 1

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$
2
  • $\begingroup$ Sounds like a good enough answer to show that the bound is finite. $\endgroup$
    – Element118
    Oct 13, 2015 at 14:06
  • $\begingroup$ Finite and quite small, I'd say. $\endgroup$ Oct 13, 2015 at 14:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .