Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
What have you tried? Why are you interested in this problem? –  Matthew Conroy Jan 11 '14 at 21:19
@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 1

up vote 1 down vote accepted

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.

share|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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