# Large Sieve Method for Weird Prime Problem

I've been working on a problem now, but I'm having a difficult time due to my lack of familiarity with sieve methods (this is not a hw problem or anything like that btw)

Let $P$ be the set of all prime numbers up to $p$, and suppose that a negative integer $N$ and a positive integer $M$ are both co-prime to all elements of $P$.

If $S=\{(N+1,M-1),(N+2,M-2),...,(N+(p^2-1),M-(p^2-1))\}$ (note that the pair $(N+x,M-x)$ is one element), is there a known sieve method for determining a lower bound on the size of $R$, where $R$ is the set of all elements of $S$ such that neither $N+x$ nor $M-x$ is divisible by any element of $P$?

• First of all, assuming $N$ positive and using $N-1,N-2,...,$ does not change the problem. Then the pairs get $(N-1,M-1),(N-2,M-2),...$. – Peter Sep 7 '15 at 15:57
• The scheme of the Erathostenes sieve probably cannot be immitaded, but you can cancel the elements divisible by $2$, then cancel the remaining elements divisible by $3$, and so on. If you do not consider the cancelled elements in the further process, you should get the elements coprime to $p\#$ in a reasonable amount of time. – Peter Sep 7 '15 at 16:01

Consider $N=1=-M$.
Then $R=a-b$ where $p_a$ is the largest prime number less than $p_b^2 -1$.
This is because all the totatives of the $b$th-primorial (all numbers not divisible by a prime less than or equal to $p_b$) upto $p_b^2$, are the prime numbers between $p_b$ and $p_b^2$. So if $p_a$ is the largest prime less than $p_b^2 -1$, then the size of $R$ is $a-b$
Next consider $N=X=-M$. Then the question amounts to "given a sequence of consecutive numbers of length $p_b^2 -1$, how many members must be totative of the $b$th primorial?" Well this question is currently unknown.
As for the case where $N \neq -M$, well the complexity increases again, and is probably unknown.