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!

  • $\begingroup$ @user2943324 a range for $a$ ?why? $\endgroup$ – Konstantinos Gaitanas Jan 11 '14 at 21:24
  • $\begingroup$ @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. $\endgroup$ – Calvin Lin Jan 11 '14 at 21:58
  • $\begingroup$ @CalvinLin i made an edit now i am much more precise. $\endgroup$ – Konstantinos Gaitanas Jan 12 '14 at 1:01

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.

  • $\begingroup$ So we don't know anything about $|G_A|$?I know that is related to $j(n)$ but how exactly? $\endgroup$ – Konstantinos Gaitanas Jan 12 '14 at 10:03
  • $\begingroup$ 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. $\endgroup$ – Greg Martin Jan 12 '14 at 17:55

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.