Let:
- $A=\{s,s+1,s+2,...,t\}$. Where $s,t$ are some fixed natural numbers
- $A(d,a,b)=\{m\in A: d|(m-a) \vee d|(m-b)\}$, where $d,a,b\in \mathbb{N}$
- $C$ be a finite subset of prime numbers
- $B =A\setminus \bigcup_{p\in C}A(p,a,b)$
Calculate/find formula for $|B|$. If it is impossible, the find nontrivial lower bound.
Here is what i have tried:
$$|B|=|A|-\sum_{i=1}^{|C|}(-1)^i\sum_{\{i_1,...,i_s\}\subset C}|A(i_{1},a,b)\cap ...\cap A(i_{s},a,b)|$$
I have used here an inclusion-exclusion formula.
If we put $a=b=0$, then $A(d,a,b)=A(d,0,0)=\{m\in A:d|m\}$
And we see that for relativiely prime $Q$ and $W$ we get $A(Q\cdot W, 0,0)=A(Q,0,0)\cap A(W, 0,0)$.
Furthermore $|B|=\sum_{d|D}\mu(d)A(d,0,0)$, where $D$ is a product of all the elements from $C$, and $\mu$ is a Möbius function
It seems, that we can't make a similar result for any other $a, b$
Please correct me if i am wrong.
Regards
Not sure if it is what's expected but
$D =\prod_{p\in C} p$ $$|B|=\sum_{m\in [s,t],\ \gcd(m-a,D)=1 \ and \ \gcd(m-b,D)=1}1 $$ $$=\sum_{m\in [s,t]}\ \ \sum_{k| \gcd(m-a,D)}\mu(k)\sum_{l| \gcd(m-a,D)}\mu(l)$$ $$ =\sum_{k| D}\sum_{l| D}\mu(k)\mu(l)\sum_{m\in [s,t], k | m-a \ and \ l|m-b}1 $$
If $\gcd(k,l)$ doesn't divide $a-b$ then $$\sum_{m\in [s,t], k | m-a \ and \ l|m-b}1=0$$ otherwise $$\sum_{m\in [s,t], k | m-a \ and \ l|m-b}1=\frac{t-s}{lcm(k,l)} +O(1)$$ (here we can precompute the unique residue class $\bmod lcm(k,l)$ which satisfies $m\equiv a\bmod k,m\equiv b\bmod l$ if we want an exact formula)
Thus we are left with
$$|B|=\sum_{k| D,l| D, \gcd(k,l)|a-b}\mu(k)\mu(l) (\frac{t-s}{lcm(k,l)}+O(1))$$ $$ =(t-s)\eta +O(4^{|C|})$$