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$?

  • $\begingroup$ 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),...$. $\endgroup$ – Peter Sep 7 '15 at 15:57
  • $\begingroup$ 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. $\endgroup$ – 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.


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.