Similar to PIE but works quite exact in this case, why?

71 Views Asked by At

Take a number. $n=100,000$ suppose. To get the count of numbers less than $n$ which are coprime to $2,3,5,7,11,13$, we can use Principle of Exclusion-Inclusion. In that case, we will consider terms like $\bigg\lfloor\frac{100,000}{p_1p_2\cdots}\bigg\rfloor$ where $p_i$ are the primes.

But there's a very li'l amount of difference when the product of primes in the denominator divide $n$ and when they don't divide it. It's differs by something $<1$.

Had it been the case when they divided $n$, the answer would've been $\Bigg(100,000-100,000\big(1-\frac{1}{2}\big)\big(1-\frac{1}{3}\big)\big(1-\frac{1}{5}\big)\big(1-\frac{1}{7}\big)\big(1-\frac{1}{11}\big)\big(1-\frac{1}{13}\big)\Bigg)$

But here it's not the case where all the primes divide $n$, but still the round figure of the above result holds exact.

Why so? Can anyone explain me that? As I said, there's a very li'l amount of difference when the product of primes in the denominator divide $n$ and when they don't divide it. It's differs by something $<1$. Even then, small differences together can make a huge difference but here it doesn't happen?

Can I get a rigorous proof instead of intuitive proofs? I think rigorousness is possible here as I have mentioned the value of $n=100,000$ and also the primes $(2,3,5,7,11,13)$.

Now, tell me if this holds for any $n$ and a set of $x$ number of primes or not. If so, explain that. If not, still explain. What my intuition says is that it will hold when $n$ goes bigger and $x$ is as small as possible. The bigger the $x$, the less will be the precision. This is what I believe. Can't justify with rigour.

Thanks a lot StackExchangers!!

1

There are 1 best solutions below

5
On BEST ANSWER

If the statements $n$ is coprime to $2$ and $n$ is coprime to $3$ were independent, we wouldn't have to worry about inclusion-exclusion. There would be some fraction coprime to $2$ and the fraction of those coprime to $3$ would be the same fraction as the fraction of $n$. That would make the multiplication exact. As you say, that works any time $n$ is a multiple of $6=2 \cdot 3$ With your larger set of primes, the computation assuming independence will be exact when $n$ is a multiple of $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13=30030$

We can look at how close it is for the primes $2,3,5$. Multiplication predicts that $\frac {1 \cdot 2 \cdot 4}{2 \cdot 3 \cdot 5}=\frac 4{15}$ of the numbers will be coprime to all of these. We can see how close it is $$\begin {array} {r r r r}n&coprime up to n&prediction&error\\1&1&0.266667&0.733333\\2&1&0.533333&0.466667\\3&1&0.8&0.2\\4&1&1.066667&-0.06667\\5&1&1.333333&-0.33333\\6&1&1.6&-0.6\\7&2&1.866667&0.133333\\8&2&2.133333&-0.13333\\9&2&2.4&-0.4\\10&2&2.666667&-0.66667\\11&3&2.933333&0.066667\\12&3&3.2&-0.2\\13&4&3.466667&0.533333\\14&4&3.733333&0.266667\\15&4&4&0\\16&4&4.266667&-0.26667\\17&5&4.533333&0.466667\\18&5&4.8&0.2\\19&6&5.066667&0.933333\\20&6&5.333333&0.666667\\21&6&5.6&0.4\\22&6&5.866667&0.133333\\23&7&6.133333&0.866667\\24&7&6.4&0.6\\25&7&6.666667&0.333333\\26&7&6.933333&0.066667\\27&7&7.2&-0.2\\28&7&7.466667&-0.46667\\29&8&7.733333&0.266667\\30&8&8&0 \end {array}$$ If we had started at $0$ all the predictions would have been $\frac 4{15}$ higher.