In the context of sieving for twin primes ($p\#$ is the primorial function) the following seems true.

The number of $n$ such that $n, (n+2)$ are coprime to $p_k\#$ for $n=1,2,...,~p_k\#$ is $\prod_{i=2}^k (p_i-2).$

Calculation of the first 7 products and a bit of luck in OEIS suggest this is true but it does not seem so easy to prove. I notice that $n+2$ is a simple permutation of $GCD(n,p_k\#)$ and so maybe using characters? Partly I am posting this because I haven't seen it before so someone else might find it interesting. It does not lead (directly) to a useful sieve because $p_k\#$ grows too fast but probably it has been considered somewhere.


Let me consider $p_k$ primes.

According to the Chinese Remainder Theorem every number $n$ from $1$ to $p_1p_2\cdots p_k$ is uniquely determined by the set of its $k$ remainders $r_i$ when $n$ is divided by $p_i$.

In practice to every choice of remainders $r_i$ corresponds one and only one number $n$ from $1$ to $p_1p_2\cdots p_k$.

So, we can ask, in how many ways can we choose remainder $r_i$ ? We want it different from 0, otherwise $n$ is divisible by $p_i$ and we want it different from $p_i-2$, otherwise $n+2$ is divisible by $p_i$.

So, apart the case of $p=2$ in which only the remainder 1 is admissible, in all the other cases there are $p_k-2$ possible remainders.

Hence, the number of sets of "good" remainders (and thus the number of "good" pairs) is just $$(p_2-2)(p_3-2)\cdots (p_k-2) $$

as you imagined.


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.