I was playing around with prime numbers, and specifically how many numbers we can exclude from an interval from being primes. It is easy to see, that after $2$, the ratio of numbers is $1-\frac{1}{2}$, as we know every second number to be divisible by $2$ and, as such be impossible to be a prime. After we include $3$, the ratio would be $1-\frac{1}{2}-\frac{1}{3}$, except that every number divisible by $6$ would be excluded once by the $\frac{1}{2}$ and a second time by the $\frac{1}{3}$. Therefore in the actual ratio we have to add every sixth number again. So the actual ratio is $1-\frac{1}{2}-\frac{1}{3}+\frac{1}{6}$. And naturally I wondered how this sequence continues once we include $5$. However, the number of terms grows rapidly. This is because
1: We have to add back every tenth and fiveteenth number, again, as we would otherwise subtract them twice by the $\frac{1}{2}$ and $\frac{1}{5}$ or the $\frac{1}{3}$ and $\frac{1}{5}$ respectively.
2: We have to subtract every $30$eth Number, as we subtract them thrice from the $2,3,5$ and add them back thrice from the $6,10,15$, so as to not ignore these, we subtract them.
This is the sequence I have arrived at, although I could be missing something
$1-\frac{1}{2}-\frac{1}{3}+\frac{1}{6}-\frac{1}{5}+\frac{1}{10}+\frac{1}{15}-\frac{1}{30}$
Conjectured sequence
If we look at the number of terms, the sequence $1,2,4,8$ appears, furthermore, if we look at the latter half of our sequence for the first 3 prime numbers $(-\frac{1}{5}+\frac{1}{10}+\frac{1}{15}-\frac{1}{30})$, it is just the first half $(1-\frac{1}{2}-\frac{1}{3}+\frac{1}{6})$ multiplied by $-\frac{1}{5}$. So here is my conjecture stated a bit more mathematically:
Let $p_n$ be the $n$-th prime number, $r(n)$ the ratio of natural numbers divisible by the first $n$ prime numbers to the natural numbers, then
\begin{multline}
r(0)=1,\\
r(n+1)=r(n)-\frac{1}{p_{n+1}}r(n)\\
=r(n)\cdot\left(1-\frac{1}{p_{n+1}}\right)\\
=r(0)\cdot\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)…\left(1-\frac{1}{p_{n+1}}\right)\\
=\prod_{i=1}^{n+1}\left(1-\frac{1}{p_i}\right)
\end{multline}
My question is: is this true? It seems true but again, as the number of terms grow so rapidly I could have missed something. I am also very certain, that I was not the first to have this idea, but I failed to find any theorem like this on google.
Best Answer
Yes, this is true. You’ve reinvented the inclusion–exclusion principle, Möbius inversion and Euler’s totient function.