2

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

mkultra
  • 1,382
  • 1
    If $d \ \nmid \ a-b$ then $d$ can't divide both $m-a$ and $m-b$ so $A(d,a,b) = \lfloor (t-a)/d\rfloor-\lfloor (s-a-1)/d\rfloor +\lfloor (t-b)/d\rfloor-\lfloor (s-b-1)/d\rfloor$. If $d \ | \ a-b$ then $A(d,a,b) = \lfloor (t-a)/d\rfloor-\lfloor (s-a-1)/d\rfloor$. The lower bound will be of the form $x t-ys-z$. – reuns Nov 27 '20 at 01:32
  • Thank you. How to calculate for example $|A(d_1,a,b)\cap A(d_2,a,b)|$? How do you know that the lower bound will be of this form? – mkultra Nov 27 '20 at 09:51
  • Your assertion is equivalent to: $(p_1\lor p_2)\land(q_1 \lor q_2)\iff (p_1\land q_1)\lor (p_2\land q_2)$ But this is not true. – mkultra Nov 28 '20 at 19:05
  • Yes you are right – reuns Nov 28 '20 at 20:24
  • Anything unclear – reuns Nov 29 '20 at 13:02
  • @mkultra, out of curiosity, where does this problem statement come from? – user3733558 Feb 04 '21 at 13:17

1 Answers1

1

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|})$$

reuns
  • 77,999