# Sieving integers

Let $2=p_1,p_2,\cdots ,p_n$ be the first $n$ prime numbers.
Suppose $N$ is a natural number and that $A=\{a+1,\cdots, a+N\}$ be a set of $N$ consecutive integers.
Let $P_n=p_1\cdot p_2\cdot \cdots p_n$ and $G_A=\{x:x\in A : \gcd(x,P_n)=1\}$
What is the maximum value of $|G_A|$?
In other words:At least how many integers from the set $A$ will be sieved by the first $n$ primes?

I would like to see (if it is possible) an elementary method-result .
Thanks in advance!

• @user2943324 a range for $a$ ?why? – Konstantinos Gaitanas Jan 11 '14 at 21:24
• @panoramix I am confused by what you meant by "an asymptotic function of N". Can you clarify? I was thinking that you meant $N \rightarrow \infty$, but I see that's not the case. – Calvin Lin Jan 11 '14 at 21:58
• @CalvinLin i made an edit now i am much more precise. – Konstantinos Gaitanas Jan 12 '14 at 1:01

## 1 Answer

We don't understand this situation as well as we would like to, particularly when $A$ is between say $n$ and $n^2$. It's related to the Jacobsthal function on primorials, if you want to do some digging around.

• So we don't know anything about $|G_A|$?I know that is related to $j(n)$ but how exactly? – Konstantinos Gaitanas Jan 12 '14 at 10:03
• One talks about how few integers could be sieved out, the other about how many integers could be sieved out. I thought pointing out the mysterious nature of the latter might give you insight as to the difficulties of the former. In general, the smaller $N$ is relative to $n$, the harder the problem is - that's what sieve theory tries to address as best it can. – Greg Martin Jan 12 '14 at 17:55