# How many random sieve operations to decimate the set {2,…,n}?

Let $S$ be the set of integers $\{2,3,4,\ldots,n\}$. Consider the following process:

• Select a random element $k \in S$.
• Remove from $S$ every number divisible by $k$.
• Repeat with this reduced $S$.

I am interested in the number of repetitions $\sigma(n)$ needed to reduce $S$ to the empty set.

Example, $n=10$: \begin{eqnarray} \# &:& 2,3,4,5,6,7,8,9,10\\ 10 &:& 2,3,4,5,6,7,8,9\\ 9 &:& 2,3,4,5,6,7,8\\ 3 &:& 2,4,5,7,8\\ 4 &:& 2,5,7\\ 5 &:& 2,7\\ 7 &:& 2\\ 2 &:& \varnothing \end{eqnarray} Limited data suggests that the number of sieve operations $\sigma(n)$ needed to decimate the set $S$ might grow approximately linearly with $n$: Number of random sieve iterations to decimate the set $\{2,3,\ldots,n\}$.
Each point plotted is the average of $10$ simulations.
The slope is about $0.28$ (without any careful statistics).

Perhaps it is possible to estimate $\sigma(n)$ for large $n$?

• You will need $\pi(n)$ at the absolute minimum, and in the first draw you should expect to knock out on average less than log n entries. My guess is that $C\pi(n)$ tries are needed where $C$ may grow with $n$. Gerhard "Or It Could Be Three" Paseman, 2015.11.15 – Gerhard Paseman Nov 15 '15 at 8:19
• I did an experiment with $n=1000000$ and found $\sigma(n)=235992$ in my instance. This doesn't appear to agree with the $C\pi(n)$ guess. – Anthony Quas Nov 15 '15 at 12:45
• As $\pi(10^6)=78,498$, I'd say it supports the guess that $C$ is near 3 when $n$ is a million quite well. Gerhard "Is Looking At It Differently" Paseman, 2015.11.15 – Gerhard Paseman Nov 15 '15 at 17:13
• There may be tree-pruning mathematics which is available. Joseph is essentially pruning a subset of the divisibility lattice, and the answer may apply to posets on which a Moebius function is defined. Gerhard "Ok, Maybe Vine-pruning Mathematics Instead" Paseman, 2015.11.15 – Gerhard Paseman Nov 15 '15 at 21:33

## 2 Answers

An equivalent way of describing the process: We start with a randomly chosen permutation $\tau$ of $\{2, \dots, n\}$. At each step we choose the first number in $\tau$ which is still in our set $S$, and apply the deletion process with that as our $k$. A key property here:

An integer $x$ is chosen at some point if and only if x appears before all of its divisors in $\tau$

This is simply because if some divisor $y$ of $x$ appears before $x$, then either $y$ itself is chosen, or some divisor of $y$ (which is also a divisor of $x$) is chosen.

In particular, the probability that $x$ is chosen at some point is $\frac{1}{d(x)-1}$, where $d(x)$ is the number of divisors of $x$. This implies that the expected number of steps to decimation is $$\sum_{x=2}^n \frac{1}{d(x)-1}$$

I feel like this sum (or at the very least $\frac{1}{d(x)}$) has to be well-studied, but I don't have any references.

• That's very nice. A standard argument (Selberg-Delange) will show that $\sum_{k=2}^{n} 1/d(k)$ is about $Cn/\sqrt{\log n}$ for a constant $C$. And your sum is asymptotically the same up to error terms that are smaller. – Lucia Nov 15 '15 at 15:15
• Very clever reformulation of the problem! – Joseph O'Rourke Nov 16 '15 at 1:35

I think the correct asymptotics should be rather $O(\frac{n}{\log n})$. That's because when you have $n$ numbers in your set and $n$ is large, then you knock out roughly $U^{-1}$ numbers, where $U$ is a Uniform$[0,1]$ random variable (indeed, if $k$ is chosen, then you through out approximately $\frac{n}{k}=\big(\frac{k}{n}\big)^{-1}$ numbers). Now, $\sum_{j=1}^m U_j^{-1}$ grows roughly as $m\log m$, so you need around $O(\frac{n}{\log n})$ steps to "considerably decrease" you set (say, to the size of $\frac{n}{\log n}$, since then it's enough to just decrease linearly).

Hopefully, this heuristics can be turned into proof, since on the "early stages" the "double-erasing attempts" (i.e., when you try to remove a number that was already removed before) shouldn't contribute a lot.

• I also thought about this heuristic, but I feel it might not be right. It's true that you delete on average $\log n$ numbers in your first step, but (1) much of this is accounted for by very small divisors - which can only be used once; and (2) once you've used up a small divisor, later removals kill off a lot less. My money is on $\Omega(n)$. (Also in the computer experiment, you see a lot of time where "nothing" is being deleted and $\sigma(n)/n$ decreases from $0.28$ when $n=1000$ to $0.24$ when $n=1000000$.) – Anthony Quas Nov 15 '15 at 19:50
• Now I think that the other answer ($\Omega(n/\sqrt{\log n})$) may be true, but I'm pretty sure it should be $o(n)$ in any case. Well, just intuitive feeling :) – Serguei Popov Nov 15 '15 at 21:15