1
$\begingroup$

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()

enter image description here

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.

$\endgroup$
1
  • 2
    $\begingroup$ $\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$. $\endgroup$
    – MJD
    Sep 30, 2022 at 2:57

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – Galen
    Sep 30, 2022 at 2:49
3
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .