TITLE: At what rate are composites removed in a set after each prime multiple is cancelled out?
QUESTION [1 upvotes]: I was looking at sieves today, mainly sieving for primes and I noticed a pattern type thing. As I crossed out primes in a small set, the number of composites that were crossed out decreased. I haven't tested this for larger sets but I reckon it won't be as quick. So I had the following question: 

Given a set of numbers, at what rate do the number of composites decrease after each prime is cancelled out?

So for example, I have the following sieve
$$\begin{array}{ccccccccc}
2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 &10 \\
11 & 12 & 13 & 14 & 15& 16& 17 & 18 & 19 \\
20 & 21 & 22 & 23 & 24 & 25 &26 & 27& 28 \\
\end{array}$$
Now when I begin to sieve out the primes, by cancelling out multiples of $2$
$$\begin{array}{ccccccccc}
\require{cancel}
2 & 3 & \cancel{4} & 5 & \cancel{6} & 7 & \cancel{8} & 9 & \cancel{10} \\
11 & \cancel{12} & 13 & \cancel{14} & 15& \cancel{16}& 17 & \cancel{18} & 19 \\
\cancel{20} & 21 & \cancel{22} & 23 & \cancel{24} & 25 &\cancel{26} & 27& \cancel{28} \\
\end{array}$$
So you can see that $46$% of the numbers are already gone (of course) and then we continue with $3$. The number of multiples that are cancelled out are only $4$ and then when we continue to $5$, it is only $1$. So you can see that the number of numbers that are crossed out decreases rapidly after each prime, which makes sense but is there a general rate at which this happens? Like some number or some formula that one can apply to find that rate given a set?  
Thanks!

REPLY [1 votes]: I am not sure about what you wanted to mean by 'rate'...I am trying to give a possible answer.
Suppose you have the set $A=\{n\le x:n\in\mathbb{N}\}$ and you want to execute a sieving process on this set. Define $$T(n):=\#A_{p_n},\text{where$A_{p_n}$ is derived set after sifting by prime $p_n$}.$$Assume $T(0)=\#A$, recursively we can have,
$$T(n)=T(n-1)-\#\{m\in A_{p_{n-1}}:p_n|m\}.$$ Let, $z>x$ and define $P(z):=\prod\limits_{p<z}p$. Now by simple inclusion-exclusion principle (as Legendre did) we have, $$\#\{m\in A_{p_{n-1}}:p_n|m\}=\sum_{d|P(z)\ \ {p_n|d}}\mu(d)\lfloor{x\over d}\rfloor=-\sum_{d|{p(z)\over p_n}}\mu(d)\lfloor{x\over dp_n}\rfloor$$$$=-{x\over p_n}\prod_{p_n\neq p<z}\left(1-{1\over p}\right)+\sum_{d|{p(z)\over p_n}}\mu(d)\{{x\over dp_n}\}.$$
Now using Merten's estimate above product $O\left({1\over\log z}\right)$. So you want to define rate of decrease of composite as $T(n-1)-T(n)$ that will be roughly $O\left({x\over\log z}\right)$. Choose $z$ as you wish.
{"set_name": "stack_exchange", "score": 1, "question_id": 455818}