# Is the natural density of a counting number being divisible by 3 or 5 approximately 0.47?

I ran the following calculation to estimate the natural density of a counting number being divisible by 3 or 5 as follows:

import numpy as np
import matplotlib.pyplot as plt

matches = []
N = 10**4
for n in range(N):
if n % 3 == 0 or n % 5 == 0:
matches.append(1)
else:
matches.append(0)

means = np.cumsum(matches) / np.arange(1, N+1)
plt.plot(means)
plt.xlabel('n')
plt.ylabel('$$f_n$$')
plt.show()


The calculated result for $$f_{10^4} \approx 0.4667$$.

Only as I was typing up this question did the site recommend I read this post which led me to this answer which suggests I simply calculate

$$1 - \left(1 - \frac{1}{3} \right)\left(1 - \frac{1}{5} \right)$$

which gets 0.46666666666666656. But I will confess I don't know where this formula comes from or why it works.

• $\frac13$ of all numbers are divisible by $3$, and $\frac15$ are divisible by $5$. The sum of these is $\frac13+\frac15$. But oops, this counts each multiple of $15$ twice, once as a multiple of $3$ and once as a multiple of $5$. So we subtract out the double-counted multiples of $15$, and the answer is $\frac13+\frac15-\frac1{15}=\frac7{15}\approx0.4667$.
– MJD
Sep 30, 2022 at 2:57

This is essentially a very simple form of the Inclusion Exclusion formula.

Basically, it is easier to ask when your divisibility criterion is NOT satisfied (and then take the complement).

In our case, roughly $$\frac{2}{3}=1 -\frac{1}{3}$$ of the numbers are not divisible by $$3$$ while roughly $$\frac{4}{5}=1 -\frac{1}{5}$$ of the numbers are not divisible by $$5$$.

By the product rule, to "miss" both is the same as multiplying those odds, namely: $$\frac{2}{3}\frac{4}{5} = \frac{8}{15} = 0.5\bar{3}$$.

The complement of that is about $$\frac{7}{15} = 0.46\bar{7}$$

Note: One has to be careful when using a distribution on infinite sets like $$\mathbb{N}$$ but this logic works well here. If you work in $$\mathbb{Z}_{15}$$ you can make this precise.

• Both answers are helpful (+1 to both of you). I am not usually this torn about accepting one answer over another, but yours was easier to understand at a glance so I am accepting it. Sep 30, 2022 at 2:49

Let's consider the numbers between $$1$$ and $$15 = 3 * 5$$ . Then, $$n$$ is divisible by $$3$$ or by $$5$$ iff $$gcd(n, 15) \neq 1$$. We have that $$\phi(15) = 15 (1-\frac{1}{3})(1-\frac{1}{5})$$ , where $$\phi$$ is Euler's totient function. Therefore, the number of numbers between $$1$$ and $$15$$ that is a multiple of $$3$$ and $$5$$ is $$15 - \phi(15)$$. The proportion is therefore $$1 - \phi(15) / 15$$, which is the formula you have.

See here for a formula for Euler's totient function.