Approximation formula for a simple counting problem

45 Views Asked by At

enter image description hereLet $a,b,c$ be positive integers with $\gcd(a,b)=\gcd(a,c)=\gcd(b,c)=1$ and let $n =$ the number of positive integers $\leq N$ not divided by $a,b,c$. Set, $$m = N\cdot (1-1/a)(1-1/b)(1-1/c).$$

I noticed that $|n-m|$ is a "small" number, for all the choices of $a,b,c,N,$ I made. In fact $|n-m|<3$ in all the experiments. See the attached figure (for the specific experiment I picked $N=5000$ and $a,b,c$ randomly from [1,500], prime to each other.)

Has anyone seen the previous formula?

1

There are 1 best solutions below

1
On BEST ANSWER

Too long for a comment.

An inclusion-exclusion argument shows the exact value is: $$\begin{align}n=N&-\left(\lfloor N/a\rfloor +\lfloor N/b\rfloor + \lfloor N/c\rfloor\right) \\&+\lfloor N/(ab)\rfloor +\lfloor N/(ac)\rfloor +\lfloor N/(bc)\rfloor \\&-\lfloor N/(abc)\rfloor \end{align}$$

where $\lfloor x\rfloor$ is the "greatest integer" function.

Your expression $m$ is just the same without the $\lfloor\cdot \rfloor$ calls.

It will certainly be hard to be off by $3$ or more - you essentially need the difference $x/y-\lfloor x/y\rfloor$ to be large when $y=a,b,c,abc$ and small when $y=ab,ac,bc.$ I'm not sure if this is possible.