2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ you are right. Thank you. $\endgroup$ – 111 Sep 14 '19 at 22:29

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.